-2
$\begingroup$

I was having a conversation with a private key cryptologist who claimed they created and distributed, in the early 1990s, all 32 bit primes on 1 640Mb CD-ROM, which could also used for immediate lookup of resulting prime factors, is that even possible, in early 1990s?

They also claimed that design has been upgraded over 3 decades to do the same in DRAM or SSD for 512 (and more) bits, is that possible?

$\endgroup$
2
  • 4
    $\begingroup$ I’m voting to close this question because it's just a IT professional technique, and not particularly specific to cryptography. $\endgroup$
    – DannyNiu
    Nov 12, 2023 at 6:02
  • $\begingroup$ I think this question can and should be interpreted to be about frequency of primes, and factoring techniques which use large prime tables, and their practicality given hardware limitations. $\endgroup$
    – Meir Maor
    Nov 13, 2023 at 9:37

3 Answers 3

5
$\begingroup$

The claim "all 32 bit primes on one 640 MByte CD-ROM by 1990" is entirely reasonable. There are $203{,}280{,}221<2^{27.6}$ primes of at most 32 bits (see OEIS A007053), and that fits a CD-ROM while keeping the ability to search for a given prime in a single access, using mild compression (as noted in comment, primes above $3$ are either $1$ or $5$ modulo $6$, allowing a $179\,$MByte bitmap to encode primes to $2^{32}$). Using sieving techniques over successive intervals, it takes feasibly little time and memory to generate this, even with a personal computer of the times. CD-R existed, making the investment modest.

However, that's pointless from a cryptographic standpoint. We have many efficient methods to factor out 32-bit primes from any integer up to many thousands bits, that work nicely without such a list. One example is Pollard's rho.

The claim "same for 512 bits" is plain laughable, regardless of media and date. There are over $2^{503}$ primes of at most 512 bits, by the first order approximation $\pi(n)\approx n/\ln(n)$. For comparison, while estimates of the number of quarks in the universe varies wildly according to sources, I did not find one larger than $2^{280}$. Thus we'd need to encode $>2^{223}$ primes per quark.

However, it was already easy and commonplace in 1990 to test if a 512-bit integer is prime, or find a 512-bit prime integer.

$\endgroup$
1
  • 1
    $\begingroup$ Storing a bit array of $6n\pm1$ would take only 170 MB and lookup would be faster, but it's still pointless. $\endgroup$
    – benrg
    Nov 12, 2023 at 17:14
2
$\begingroup$

Lookup from a CD is really really slow. Building a list of all 32bit primes in the early 90s very plausible, putting it on a CD? didn't count them, but sounds about correct. Using them as a lookup? probably not. Maybe as a sieve, not exactly "an immediate lookup" reading from CD(or more likely a magnetic hard drive data was copied to) fetching the next bunch of primes to check. I don't remember seek time for CDs in the 90s but for a good magnetic hard drive it was around 20ms (and didn't improve much since). If you want to factor a 64 bit number and want to do trial division, and had the primes on a CD you could do this, and the division would probably be insignificant va read time. No need for random seeks, just read the whole thing sequentially in large chunks. for x1 CD drive that is 90 minutes but we had x8 available so around 12 minutes to factor a 64 bit number this way. Need to compare that to QFS on let's say a 486 or early Pentium running at 66-100MHz. It might come out better.

Plausible.

$\endgroup$
2
$\begingroup$

32-bit primes only need about a little bit more than 800MB before compression: http://umopit.ru/CompLab/primes32eng.htm , 512-bit would probably be impossible, since we're still using 64-bit operating systems, so file sizes and filesystem sizes are typically limited to 16EB, which isn't enough for all of the 512-bit primes.

$\endgroup$

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