# Is prime factorization by simple algorithm impossible?

**URL:** <https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159>\
**Category:** Factual Questions\
**Created:** [January 21, 2019, 5:52pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159 "2019-01-21T17:52:47Z")\
**Posts on this page:** 16\
**Page:** 3

<div class="post-metadata">

**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\
**Post date:** [January 22, 2019, 5:55pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/41 "2019-01-22T17:55:53Z")

</div>

The biggest gaps between primes do indeed grow faster than the input size. I don’t know how close results like Cramer’s conjecture are to being proved, but that would suggest one can keep things polynomial.

---

<div class="post-metadata">

**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\
**Post date:** [January 22, 2019, 6:00pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/42 "2019-01-22T18:00:14Z")

</div>

> [@Hari\_Seldon](#):
>
> But is there anything like there’s always a prime between n and n+C\*log(n) for some constant C?

Isn’t that known to be false? (I’m not sure)

---

<div class="post-metadata">

**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\
**Post date:** [January 22, 2019, 6:02pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/43 "2019-01-22T18:02:50Z")

</div>

> [@rat\_avatar](#):
>
> Currently determining whether a number is prime or can be done in polynomial time but finding the next prime cannot but we also don’t know if finding the next prime is NP-complete.

For clarity: N can be tested for primality in P(log(N)) time. The next prime can be found in, at most, N\*P(log(N)) time which is polynomial in N, but exponential _in the number of bits_ of N.

> [@Hari\_Seldon](#):
>
> … Is there any known bound on prime gaps, better than Tschebyshev’s that states, IIRC, that there is always a prime between n and 2n? But is there anything like there’s always a prime between n and n+C\*log(n) for some constant C?

[This article may touch on your question](https://en.wikipedia.org/wiki/Prime_gap). Apparently, for any constant c there are infinitely many prime gaps larger than c log n log log n log log log log n (log log log n)[sup]-2[/sup]  
Paul Erdős offered a $10,000 prize to prove this, but had been dead 18 years when Ford–Green–Konyagin–Tao and, independently, James Maynard completed the proof. Wikipedia seems to be silent about the disposition of the $10,000.

---

<div class="post-metadata">

**Author:** ![rat\_avatar](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/rat_avatar/32/255_2.png) [@rat\_avatar](https://boards.straightdope.com/u/rat_avatar)\
**Post date:** [January 22, 2019, 7:47pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/44 "2019-01-22T19:47:37Z")

</div>

> [@ftg](#):
>
> Your posts are really, really hard to parse. For one thing, you are very misleading on standard algorithm analysis.
> 
> In particular, the input size, i.e., _number of bits_, is what counts in terms of talking about complexity. Esp. if using terms like NP and EXPTIME. The _value_ of a number does not apply in this context. Furthermore, no matter which one you use you definitely do _not_ get “requires EXPTIME” for any simple version of the problem. E.g., a simple sieve method is quadratic if you’re talking about the value. Which we shouldn’t be doing.
> 
> Your posts are quite garbled. Please re-explain using standard terminology with cites. Esp. about this “EXPTIME” claim.
> 
> And don’t bother dumbing it down for me. I am friends with several of the key people involved here. I was hanging out with Gary Miller when the whole Rabin fiasco happened. I was in the back seat of a car with R and A of RSA a week after their big breakthrough. I knew Shor before he got famous. So bring out the big guns.

Then it should be quite simple for you to provide a cite that shows a proof that a 64 bit computer can _find new primes_ in polynomial time.

While you dislike the term Miller–Rabin due to your personal connections, Rabin did create the probabilistic version and if you want to be pedantic Miller was not the first to make the discovery.

Miller–Rabin primality test is potentially useful for encryption breaking because the GRH it uses ensures the existence of enough primes with certain properties. But it does not reduce the need to produce a pool of primes to _test_ to _break encryption_ which is what the OP was talking about.

Note as Miller-Rabin is unsuitable for _encrypting_ data for two reasons.

[ol]  
[li]The Miller only solution depends on a assumption that isn’t proven (GRH) but is deterministic.[/li][li]The probabilistic form Miller-Rabin finds strong pseudoprimes, which despite being named “strong” still open one to malicious attacks by someone passing you pseudoprimes.[/li][/ol]  
Even if you use a linear prime finder like the following that requires O(√n/(log log n)[sup]2[/sup]) bits of space to run in linear time:

> **[Trading time for space in prime number sieves](https://link.springer.com/chapter/10.1007/BFb0054861)**
>
> A prime number sieve is an algorithm that finds the primes up to a bound n. We present four new prime number sieves. Each of these sieves gives new space complexity bounds for certain ranges of running times. In particular, we give a linear time...

For a 1024 bit key, with simplified math you need. 2.5529116337158649e+152 bits or:

232185960495904955199734095212196794412133896546396616061488058408655268230310091139861586347561318906937577846710638035372117875923517177856.00 TB of ram.

The slower form saves some space, only needing:

594910947897768854095409740280336378396803810680285153367426951187486471974084023441406694248414911128545629749623437444160843795655531954176.00 TB of ram.

The thing you are ignoring is that 2^1024 is:

179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216

When Miller-Rabin pseudoprimes has barely been proven past 64 bits.

> **[Strong Pseudoprimes to Twelve Prime Bases](https://arxiv.org/abs/1509.00864)**
>
> Let $ψ\_m$ be the smallest strong pseudoprime to the first $m$ prime bases. This value is known for $1 \\leq m \\leq 11$. We extend this by finding $ψ\_{12}$ and $ψ\_{13}$. We also present an algorithm to find all integers $n\\le B$ that are strong...

One cannot ignore the space complexity and just focus on the time complexity.

Here is the python for you to see.

```auto

import mpmath
num = 2**1024
mpmath.sqrt(num/mpmath.log(mpmath.log(num))**2)

```

Even with bit packing etc… finding the primes gets expensive and while you can do better than brute force the time complexity does become exponential within practical computing limits.

Feel free to provide me with a cite that covers this, but as almost all of these prime factorization methods haven’t been proven even close to the typical lowest key sizes I haven’t found anything.

But in simple language, with crypto keys being large you can’t make assumptions based on the efficiency of algorithms that fit within memory. As SDMB doesn’t support math formatting I can’t offer the math to do so. But if this isn’t problematic, with the interest in crypto, you should be able to find me a paper that matches your claim.

---

<div class="post-metadata">

**Author:** ![rat\_avatar](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/rat_avatar/32/255_2.png) [@rat\_avatar](https://boards.straightdope.com/u/rat_avatar)\
**Post date:** [January 22, 2019, 8:09pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/45 "2019-01-22T20:09:24Z")

</div>

Sorry had a bug in the above, it should be:

> [@](#):
>
> mpmath.sqrt(num/(mpmath.log(mpmath.log(num))\*\*2))

The cited linear time sieve that only needs O(√n/(log log n)[sup]2[/sup]) bits of space would require:

656721068651864933251365238901797777789346124834761924763964434238208264657067085515014255510306966202398431308722072940977738506407172374528 TB of ram.

For a 1024 bit key.

---

<div class="post-metadata">

**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\
**Post date:** [January 22, 2019, 9:36pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/46 "2019-01-22T21:36:00Z")

</div>

> [@rat\_avatar](#):
>
> Even if you use a linear prime finder like the following that requires O(√n/(log log n)[sup]2[/sup]) bits of space to run in linear time:
> 
> [Trading time for space in prime number sieves | SpringerLink](https://link.springer.com/chapter/10.1007%2FBFb0054861)  
> For a 1024 bit key, with simplified math you need. 2.5529116337158649e+152 bits or:
> 
> 232185960495904955199734095212196794412133896546396616061488058408655268230310091139861586347561318906937577846710638035372117875923517177856.00 TB of ram.

Perhaps you are mixing some things up? That linear prime finder finds all the primes from 1 to n; of course some space is needed if n is huge. But the problem we are considering is to start with some n and find one single prime greater than n.

---

<div class="post-metadata">

**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\
**Post date:** [January 22, 2019, 9:53pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/47 "2019-01-22T21:53:10Z")

</div>

> [@rat\_avatar](#):
>
> Then it should be quite simple for you to provide a cite that shows a proof that a 64 bit computer can _find new primes_ in polynomial time.
> 
> While you dislike the term Miller–Rabin due to your personal connections, Rabin did create the probabilistic version and if you want to be pedantic Miller was not the first to make the discovery.

Note: you specifically said finding the next higher prime above n “requires exponential runtime”. I know of nothing that proves this and is likely false. It’s really hard to find a cite for something that hasn’t apparently been proven. My searches all indicate it isn’t that hard.

If you know of a proof, give a citation to a paper. Keep in mind that for some reasons your posts are rambling and hard to follow. So please, give a link to where someone has a readable proof of what you are talking about.

Regarding Miller’s proof. He was a grad student at Berkely when Rabin came by for a visit. Miller gave a preliminary seminar presentation on his methods. Before he knew it Rabin came out with a paper giving Miller’s ideas.

Rabin did this. E.g. the proof that 2 way DFAs accept only regular languages. The journal Rabin published in went to so far as to list an _earlier date_ on the bottom of the paper than the actual one for that issue. All the other papers had the correct date. This allowed Rabin to claim priority of the proof when others had gotten their paper published before his.

It’s like the prof says in _Real Genius_. “Never forget to check your references.”

---

<div class="post-metadata">

**Author:** ![rat\_avatar](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/rat_avatar/32/255_2.png) [@rat\_avatar](https://boards.straightdope.com/u/rat_avatar)\
**Post date:** [January 23, 2019, 1:29am UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/48 "2019-01-23T01:29:25Z")

</div>

You are going to have to search for papers on gaps between consecutive prime numbers, but most of this range hasn’t been worked on.

The Dope just doesn’t work for showing this type of math, as an example this is just unreadable.

G(x) ≥ f(x) log(x)log(log(x)log(log(log(x)))/(log(log(log(x))))[sup]2[/sup]

Cramér’s conjecture helps you out if you control the way that you generate random numbers for encrypting but for breaking ecryption the work load increases to the point of almost being brute force.

Here is a proof on Paul Erdős conjecture about Cramér’s conditional proof semi-related to the above task.

[http://annals.math.princeton.edu/2016/183-3/p04](http://annals.math.princeton.edu/2016/183-3/p04)  
Here is a link to a site showing that even for trivial to generate sequences like Fermat numbers that this is non-trivial.

[What probability to find a divisor for Fermat numbers?](http://www.fermatsearch.org/math.html)

The [prime number theorem](https://en.wikipedia.org/wiki/Prime_number_theorem) states the number of primes not exceeding _x_ is asymptotic to _x/log(x)_.

Then realize that those are the keys you have to test per number, thus O(n[sup]k[/sup]) if you don’t have enough memory for the linear methods mentioned above.

We can disagree about how sub-exponential is defined and if that is sub-exponential but it still ends up being brute force for crypto key sizes and algorithms that are safe to use. Using smooth numbers has to be avoided for security reasons as an example:

> **[ROCA vulnerability](https://en.wikipedia.org/wiki/ROCA_vulnerability)**
>
> The ROCA vulnerability is a cryptographic weakness that allows the 
> private key of a key pair to be recovered from the public key in keys generated by devices with the vulnerability. "ROCA" is an acronym for "Return of Coppersmith's attack". The vulnerability has been given the identifier CVE-2017-15361.
> The vulnerability arises from a problem with an approach to RSA key generation used in vulnerable versions of a software library, RSALib, provided by Infineon Technologies, and incorporated into...

So you should be flipping this around, if you can trivialize this you will be famous. But there is a reason that smaller keys have been abandoned a long time ago, especially ones that would fit within practical memory for some of these linear time methods.

---

<div class="post-metadata">

**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\
**Post date:** [January 23, 2019, 2:06am UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/49 "2019-01-23T02:06:23Z")

</div>

> [@rat\_avatar](#):
>
> You are going to have to search for papers on gaps between consecutive prime numbers, but most of this range hasn’t been worked on.
> 
> The Dope just doesn’t work for showing this type of math, as an example this is just unreadable.
> 
> G(x) ≥ f(x) log(x)log(log(x)log(log(log(x)))/(log(log(log(x))))[sup]2[/sup]

That is a nice result and the methods used to prove it are worthy of study by anyone interested in the subject, but it is not an exponential gap (and the conjecture is that there is no exponential gap, just (log x)[sup]2[/sup], i.e., quadratic)

For your “paranoid crypto”, some of the algorithms described [here](https://en.wikipedia.org/wiki/Elliptic_curve_primality) can prove a number is prime in a reasonable amount of time, if that is what you mean.

---

<div class="post-metadata">

**Author:** ![rat\_avatar](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/rat_avatar/32/255_2.png) [@rat\_avatar](https://boards.straightdope.com/u/rat_avatar)\
**Post date:** [January 23, 2019, 3:10am UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/50 "2019-01-23T03:10:05Z")

</div>

> [@DPRK](#):
>
> That is a nice result and the methods used to prove it are worthy of study by anyone interested in the subject, but it is not an exponential gap (and the conjecture is that there is no exponential gap, just (log x)[sup]2[/sup], i.e., quadratic)
> 
> For your “paranoid crypto”, some of the algorithms described [here](https://en.wikipedia.org/wiki/Elliptic_curve_primality) can prove a number is prime in a reasonable amount of time, if that is what you mean.

You have to keep trying numbers until you find one that is prime.

You are missing the difficulty in **breaking** encryption, not randomly finding a convenient set of random numbers. When you are **encrypting** something you only care that you and your _intended recipient_ agree and that neither of you picks a pseudorandom numbers.

When you are **breaking** encryption you can’t just randomly skip prime encryption values that some of these faster methods that are useful for **encrypting** data.

---

<div class="post-metadata">

**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\
**Post date:** [January 23, 2019, 3:52am UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/51 "2019-01-23T03:52:38Z")

</div>

> [@rat\_avatar](#):
>
> You have to keep trying numbers until you find one that is prime.

Yes. (so?)

> [@](#):
>
> You are missing the difficulty in **breaking** encryption, not randomly finding a convenient set of random numbers. When you are **encrypting** something you only care that you and your _intended recipient_ agree and that neither of you picks a pseudorandom numbers.
> 
> When you are **breaking** encryption you can’t just randomly skip prime encryption values that some of these faster methods that are useful for **encrypting** data.

I never claimed to describe a method of fast or polynomial integer factorization that is useful for breaking encryption.

---

<div class="post-metadata">

**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\
**Post date:** [January 23, 2019, 7:25am UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/52 "2019-01-23T07:25:30Z")

</div>

[raises hand to ask a possibly stupid question]  
Suppose I choose two large numbers I believe to be prime and inform my agent in the Kremlin of their product. He starts sending me messages and I decode them.

But, unbeknownst to me, one of the two ‘primes’ I chose was just a pseudoprime: it was itself the product of two largish primes. Since it’s _almost_ a prime does the encryption/decryption _almost_ work? Assuming small message blocks are coded independently, should I expect 99% of them to be garbled? Only 1% garbled? Something in between?

---

<div class="post-metadata">

**Author:** ![Francis\_Vaughan](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/francis_vaughan/32/3093_2.png) [@Francis\_Vaughan](https://boards.straightdope.com/u/Francis_Vaughan)\
**Post date:** [January 23, 2019, 8:32am UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/53 "2019-01-23T08:32:37Z")

</div>

> [@septimus](#):
>
> [raises hand to ask a possibly stupid question]  
> Suppose I choose two large numbers I believe to be prime and inform my agent in the Kremlin of their product. He starts sending me messages and I decode them.
> 
> But, unbeknownst to me, one of the two ‘primes’ I chose was just a pseudoprime: it was itself the product of two largish primes. Since it’s _almost_ a prime does the encryption/decryption _almost_ work? Assuming small message blocks are coded independently, should I expect 99% of them to be garbled? Only 1% garbled? Something in between?

Encryption works fine. It doesn’t even need the numbers to be primes. What you have is a vulnerable encryption. In principle it would be easier to crack your encryption. In practice using the product of two large primes rather than a huge prime is actually done.

---

<div class="post-metadata">

**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\
**Post date:** [January 23, 2019, 5:47pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/54 "2019-01-23T17:47:59Z")

</div>

I am still completely baffled by Rat Avatar’s jumping all over the place. Answering questions by discussing something else, etc.

But **again** I just want to get down the the “requires exponential time” claim.

After all, good old RSA in their original [paper](http://people.csail.mit.edu/rivest/Rsapaper.pdf) give a way to find large primes: Randomly generate a 100\* digit odd number and test it. Keep going. Won’t take long to find one. (Page 9)

A. Why would sequential searching take horribly much longer?  
B. And that still doesn’t address the claim there’s a **proof** that it does?

- Ah, the good old days when 200 digit RSA keys were fine.

---

<div class="post-metadata">

**Author:** ![rat\_avatar](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/rat_avatar/32/255_2.png) [@rat\_avatar](https://boards.straightdope.com/u/rat_avatar)\
**Post date:** [January 23, 2019, 6:03pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/55 "2019-01-23T18:03:40Z")

</div>

> [@ftg](#):
>
> I am still completely baffled by Rat Avatar’s jumping all over the place. Answering questions by discussing something else, etc.
> 
> But **again** I just want to get down the the “requires exponential time” claim.
> 
> After all, good old RSA in their original [paper](http://people.csail.mit.edu/rivest/Rsapaper.pdf) give a way to find large primes: Randomly generate a 100\* digit odd number and test it. Keep going. Won’t take long to find one. (Page 9)
> 
> A. Why would sequential searching take horribly much longer?  
> B. And that still doesn’t address the claim there’s a **proof** that it does?
> 
> - Ah, the good old days when 200 digit RSA keys were fine.

The entire point it is used in encryption is that there is an easy way to generate something that is hard to reverse.

Proving that some symmetries or algebraic structures connected to prime numbers would change this story. While it is often said that proving the Riemann Hypothesis would cause this really proving it was _false_ would point to the distribution of primes having more structure than we expect.

The reason I have been insistent that these solutions we have with small numbers doesn’t apply in this thread is due to the last paragraph in the OP.

> [@WernhamHogg](#):
>
> What I want to know is if there is mathematical proof that no algorithm will ever exist to derive prime factors easily or if it’s simply assumed that no elite hacker-mathemitician will discover one.

These linear factoring methods fall down when you have more possible numbers than the number elementary particles of matter exist in the visible universe (roughly 10[sup]86[/sup]).

This is why you use two 1024-bit factors which are \> 2[sup]1023.5[/sup] as recommended in [FIPS 186-4](https://csrc.nist.gov/publications/detail/fips/186/4/final).

The computational cost is the _primary_ reason for this. While there is always a prime between “n and 2n” as mentioned before, finding the _same primes_ one someone else used is the expensive part.

Perhaps the reason you are confused about my replies is because you aren’t focusing on the question the OP had. As you just stated low bit sized modulus are useless so why offer methods that only work at low bit sizes?

---

<div class="post-metadata">

**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\
**Post date:** [January 23, 2019, 6:39pm UTC](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159/56 "2019-01-23T18:39:39Z")

</div>

> [@rat\_avatar](#):
>
> These linear factoring methods fall down when you have more possible numbers than the number elementary particles of matter exist in the visible universe (roughly 10[sup]86[/sup]).
> 
> This is why you use two 1024-bit factors which are \> 2[sup]1023.5[/sup] as recommended in [FIPS 186-4](https://csrc.nist.gov/publications/detail/fips/186/4/final).

Let’s not call it linear, it’s exponential as a function of the magnitude of the number.

> [@](#):
>
> Perhaps the reason you are confused about my replies is because you aren’t focusing on the question the OP had. As you just stated low bit sized modulus are useless so why offer methods that only work at low bit sizes?

I’m confused too, since I can in fact generate big bit sized RSA moduli on an obsolete desktop computer using those methods and even rigorously check the factors for primality. Note I cannot factor your RSA modulus on the same computer using trial division, but who said we could?

[Previous page](https://boards.straightdope.com/t/is-prime-factorization-by-simple-algorithm-impossible/828159.md?page=2)