Prime factorization project

[creeperman7002]

Quoting these posts from Thread for basic questions:

Could a pattern that factorizes arbitrary integers and displays their output be constructed?

It could probably be a similar design to the pi calculator, but it would have to be able to solve polynomials if it were using a fast algorithm like the elliptic curve method, quadratic sieve, or general number field sieve.

Obviously it would be useless in factorizing large integers because of a combination of the long time taken to factorize sufficiently large integers and the fact that it's in CGOL.

Since Life has been proven to be computationally universal, it is possible to construct a Life pattern that can emulate a Turing machine (which has actually been done), and it's possible to program a Turing machine to compute any computible function (e.g. factorization of any finite integer). This doesn't mean that doing it by emulating a Turing machine would be particularly efficient; only that it's theoretically possible.

(In a similar fashion, it's possible to construct any glider-constructible pattern from 17 gliders via constructor technology, but that doesn't mean that it's easy to describe the particular coordinates of those gliders. The entire program is deduced from the position of one remote glider - and its position is necessarily very far away, even for the simplest of constructions.)

I will be leading a project to construct a pattern that factorizes a given integer N. However, this project is just for recreational purposes because such a pattern wouldn't be efficient at factorizing integers, let alone large semiprimes. If completed, it could probably end up in POTY 2021.

[dvgrn]

I will be leading a project to construct a pattern that factorizes a given integer N. However, this project is just for recreational purposes because such a pattern wouldn't be efficient at factorizing integers, let alone large semiprimes. If completed, it could probably end up in POTY 2021.

You may find that that task is easier than you think, these days. All that you'll have to do is code up a factorization algorithm in APGsembly, compile it into a Life pattern with the existing script, and figure out how you want to handle inputting the value for N and getting the factors out as output -- probably print the factors the same way the pi calculator prints pi?

Last year Rei wrote an online APGsembly emulator -- definitely worth checking out.