For hundreds of years mathematicians have been looking for a method to quickly factorize a natural number.

For example:

3894757 = 877*4441

Today there's no way to perform prime factorization quickly (when it comes to big numbers). And cryptography is based on this fact.

What could an algorithm for fast prime factorization look like?

Is a Game Boy enough or does it take a quantum computer to run this algorithm?

Are there other ways than having an algorithm to perform prime factorization quickly?

  • 2
    $\begingroup$ This doesn't seem to be related to worldbuilding? This might be better suited for a math stack. $\endgroup$ Nov 27 '19 at 19:23
  • $\begingroup$ I'm going to suggest asking this on Mathematics.SE, they will be able to give you a more professional answer. Your question about the gameboy is a little easier to answer: You'd need a quantum computer (today anyways) $\endgroup$
    – thanby
    Nov 27 '19 at 19:23
  • 1
    $\begingroup$ Honestly, if I knew that I wouldn't publish it here for hundred million rep. I would use it to write a software and enjoy life afterwards. I leave to your imagination the intermediate step. $\endgroup$
    – L.Dutch
    Nov 27 '19 at 19:32
  • $\begingroup$ I don't know what the algorithm would look like, but the hardware to implement it would look like an answering machine. (Well, not really; it was just hidden inside a shell that looked like an answering machine. It was small enough that you could hide it inside something that looks like a Game Boy.) $\endgroup$
    – Matthew
    Nov 27 '19 at 20:08
  • $\begingroup$ I am not expecting a mathematical answer. I am expecting a science fiction answer. $\endgroup$
    – somega
    Nov 27 '19 at 20:22

Assuming this has something to deal with worldbuilding, I'll give a worldbuilding answer.

  1. Currently the best known method is to check all the primes less than the square root of the number to be factored. Quickly is a relative term, and mostly depends on the size of the primes involved. This poses a problem, as the method to factor quickly increases in speed, so does the ability to check larger and larger numbers for primality, this then increases the size of primes used to encrypt in the first place.
  2. This means that any innovation used will only provide a temporary advantage to the side that has it as long as they keep it a secret. Once the secret is out, the systems will become secure again.
  3. Any algorithm should be able to be run on any hardware, however the speed at which it can process is going to be the main issue. The super computer is going to be much faster than the game boy, and will be able to factor much larger numbers in a reasonable amount of time.
  4. The field of quantum computing has theorized that it might be possible to use a quantum computer to harness infinite computing speed (essentially it would be able to compute anything in the same amount of time regardless of computing complexity).
  • 1
    $\begingroup$ I don't believe infinite computing speed has been theorized. I believe quantum computers have been theorized to compute in a way that P = NP might be true, but that may have been given in the context that a bit could be 1 and 0, a bit can be an infinite number of values simultaneously. $\endgroup$ Nov 27 '19 at 20:28
  • $\begingroup$ Quantum computers are very much finite. The complexity class of problems they can solve, BQP intersects NP but is not known to be a superset of it, unless P=NP. $\endgroup$ Nov 27 '19 at 21:00
  • $\begingroup$ @AndrewMellor Infinite speed is perhaps the wrong term, but a quantum computer can solve certain problems in one step, can`t it? Factorisation is not one of those problems, I assume. $\endgroup$
    – Karl
    Nov 27 '19 at 22:05
  • $\begingroup$ "Currently the best known method is to check all the primes less than the square root of the number to be factored" I thought the Sieve of Eratosthenes and/or Wheel Factorisation were more efficient, although they have slightly different constraints. Still, AFAIK, they could be improved on to provide better speed. Although, to be honest, I don't know how very large numbers are usually factorised. $\endgroup$
    – VLAZ
    Nov 28 '19 at 7:19

I am unsure of how technical of an explanation you are looking for but; The Quadratic Sieve Algorithm is currently the fastest for any number under $10^{100}$.

The Quadratic Sieve Algorithm and many algorithms are based on Fermet's Factorization Method.

In Fermet's method: the idea is to find two numbers ($a$ and $b$) where:

$a^2−b^2 = n $
$n$ being the number we wish to factor.

If we can do this, simple algebra (via the Difference of two squares) tells us that:

$(a+b)(a−b) = n$

If we're lucky, we have found a nontrivial factorization of $n$;

The concept behind Fermat's algorithm is to search for an integer ($a$) such that $a^2−n$ is a square. If we find such an $a$, it follows that:

$a^2−(a^2-n) = n$
enter preformatted text here

Hence we have a difference of squares equal to $n$. The search is a straightforward linear search: we begin with the ceiling of the square root of $n$, the smallest possible number such that $a^2−n$ is positive, and increment a until $a^2−n$ becomes a square. If this ever happens, we try to factor $n$ as $(a − \sqrt{a^2−n})(a + \sqrt{a^2−n})$; if the factorization is trivial, we continue incrementing $a$.

Example from for the prime factorization of $5959$:

$a = 78$
$78^2−5959 = $ not a square

$a = 79$
$79^2−5959$ = not a square

$a = 80$
$80^2−5959 = 441 = 21^2$

Hence: $(80-21)(80+21) = 5959$,
Which gives the nontrivial factorization: $59\times101 = 5959$.

Also worth mentioning if: $\sqrt{n} > a$ or $a > n-1$, then we know $n$ has $0$ non trivial factorization.

To date all major developments; Quadratic sieve, GNFS, and Dixon's Factorization Method; have been based on Fermet's method.

  • $\begingroup$ Dude,, seriously: Mathjax. If it's any consolation, I need to learn it too. $\endgroup$ Nov 27 '19 at 20:34
  • $\begingroup$ @WeareMonica. I have added the formatting. $\endgroup$
    – overlord
    Nov 27 '19 at 21:06
  • $\begingroup$ @WeareMonica. Did you tag me in a comment and then delete it? I saw it briefly and now I can't find it and I'm confused now lol $\endgroup$
    – overlord
    Nov 27 '19 at 21:11
  • $\begingroup$ The quadratic sieve is slow. For example to factorize 1649 it takes 17 steps. Even trial division is faster. $\endgroup$
    – somega
    Nov 28 '19 at 16:20
  • $\begingroup$ @somega My source for saying it is the fastest under 100 decimal digits is: Carl Pomerance, Analysis and Comparison of Some Integer Factoring Algorithms, in Computational Methods in Number Theory, Part I, H.W. Lenstra, Jr. and R. Tijdeman, eds., Math. Centre Tract 154, Amsterdam, 1982, pp 89-139. en.wikipedia.org/wiki/Quadratic_sieve#cite_note-1 when talking about prime factorization in terms of encoding and decoding, most of the primes would be much larger than 1649 $\endgroup$ Dec 2 '19 at 15:30

Knowing what a solution to an open math problem "would look like" amounts to knowing the solution (or at least its main steps). And given that this question has not been solved, nobody knows. It may well be impossible, and therefore have no valid answer.

  • $\begingroup$ This isn't really an answer to the question. It's a valid criticism, but it's not an answer. This should probably be a Comment instead. $\endgroup$ Nov 27 '19 at 19:53
  • $\begingroup$ The point is that this is the best answer that this question can possibly get. $\endgroup$
    – Priska
    Nov 27 '19 at 19:53
  • $\begingroup$ This is a Frame Challenge answer, and such answers are considered valid on the site. I'm going to flag this as OK. $\endgroup$
    – SRM
    Nov 27 '19 at 22:40

Not the answer you're looking for? Browse other questions tagged or ask your own question.