How hard can generating 1024-bit primes be?

Re:How hard can generating 1024-bit primes be? by lifthrasiir on Friday May 03, 2024 @10:48PM (#40254416)

> Just testing all the bases from 2 through 2 log(N)^2 doesn't actually seem to be too bad for N around 2^1024. It would be a little under 1007600 bases.

Unfortunately this limit depends on the currently unproven conjecture (a subset of the generalized Riemann hypothesis). You have to check all n bases to be unconditionally correct.

[ Parent | on HN ]

Re:How hard can generating 1024-bit primes be? by djao on Saturday May 04, 2024 @03:12PM (#40259660)

Going up to n is surely excessive. You need a version of the Riemann hypothesis to get any sort of logarithmic bound, but a sqrt(n) bound can be achieved using unconditional Polya-Vinogradov type inequalities. (A successful Miller-Rabin test corresponds to a nontrivial value of a Dirichlet character, and Polya-Vinogradov ensures that the least such value cannot exceed sqrt(n) * ln(n), unconditionally without the need for any Riemann hypothesis.)

A reference for this material is "Explicit bounds for primality testing and related problems" by Eric Bach, Math. Comp. 55 (191), July 1990, pp. 355-380.

[ Parent | on HN ]

Re:How hard can generating 1024-bit primes be? by pbsd on Saturday May 04, 2024 @04:05PM (#40259943)

The best asymptotic bound is somewhere between n^(1/8sqrt(e) + eps) and n^(1/6.568sqrt(e) + eps), per [1].

[1] https://doi.org/10.1007/BFb0030409

[ Parent | on HN ]