Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs

Questions tagged [number-field-sieve]

The number field sieve is an index calculus algorithm suitable both for factoring large numbers and computing discrete logarithms in prime fields. It is currently the most effective, general, classical algorithm for solving these problems.

Filter by
Sorted by
Tagged with
1 vote
1 answer
59 views

Does the ability to factor in polynomial time give you smooth numbers in the number field sieve?

I have read that despite strong connections between prime factorization and DLP an algorithm for the former does not imply the latter directly. But I was reading about the number field sieve and it ...
Ian Campbell's user avatar
4 votes
1 answer
986 views

How did they factor RSA 240?

Since NFS runs in essentially $n^{1/3}$ time, and RSA-240 is a composite of two 120-digit primes, shouldn't this have taken at least $10^{40}$ operations, not including any overhead? Even if you could ...
The Yomster's user avatar
3 votes
2 answers
390 views

In which case number field sieve/index calculus is faster for solving discrete logarithm?

Given the normal discrete logarithm problem: $$a = b^c \mod{P}$$ with prime $P$ and numbers $a,b,c$ For which kind of $P,b$ the NFS/IC algorithm is faster than Baby-Step/Giant-Step+ Pollard's Rho ($\...
J. Doe's user avatar
  • 453
3 votes
0 answers
93 views

Subexponential algorithms that apply only one of factoring and discrete logarithm?

Shor (quantum polynomial), Number Field Sieve (subexponential), Pollard rho (square root) all have both factoring and discrete logarithm over $\mathbb F_p^*$ variants. What are the subexponential ...
Turbo's user avatar
  • 930
1 vote
2 answers
230 views

Complexity of number field sieve theorem does not match with security of elliptic curves

Number field sieve algorithm can is used to break discrete logarithm on field $F_{p^n}$. The algorithm has time complexity $\exp((c+o(1))\cdot(\log p^n)^{1/3}\cdot(\log \log p^n)^{2/3}$. Originally ...
satya's user avatar
  • 1,414
6 votes
0 answers
402 views

Precomputation attacks against ECDH

Diffie-Hellman groups are vulnerable to sieving precomputation attacks. These attacks allow a one-time computation against a given DH modulus that makes it practical to attack all subsequent key ...
forest's user avatar
  • 15.3k
4 votes
0 answers
243 views

Is the matrix step of GNFS still the hardest part?

When the factorization of RSA-768 was announced in December 2009: the sieving took about 24 months and the matrix step took 119 days (4 months). So sieving took about 6 times as long. This is despite ...
Nike Dattani's user avatar
6 votes
0 answers
191 views

What are the theoretical memory requirements for these factoring algotihms?

Given an $n$ bit integer quadratic sieve takes $L(\frac12,1+o(1))$ time and number field sieve takes $L(\frac13,1.922)$ time where $L$ notation is given in https://en.wikipedia.org/wiki/L-notation. ...
Turbo's user avatar
  • 930
1 vote
1 answer
183 views

Quadratic sieve for DLOG performance - theory vs actual?

Is there any report on comparing quadratic and number field sieve performance in theory vs actual data for discrete logarithm over primes? Is actual data better than theory in any way unexplained (I ...
Turbo's user avatar
  • 930
1 vote
0 answers
212 views

Is there any concrete working example for Function Field Sieve method?

I'm new to Function Field Sieve(FFS) (Number Field Sieve(NFS) as well) method and I'm finding it is quite difficult to understand it (especially concepts of valuation at infinity, Ca,b curves etc.) ...
Tanmay Sharma's user avatar
3 votes
1 answer
207 views

Combining Hellman Pohlig with Sieve

Suppose integer $m$ has $\phi(m)=2pq^5r^2$ where $p,q,r$ are primes. Hellman-Pohlig says that finding discrete log $z\bmod p$, $z\bmod q^5$, $z\bmod r^2$ and $z\bmod 2$ suffices to find $z\bmod\phi(m)...
Turbo's user avatar
  • 930
3 votes
1 answer
143 views

SNFS: Quantifying the "small" parameters?

The special number field sieve (SNFS) is an algorithm to calculate discrete logarithms and to factor numbers, given that the target has a special structure. Now, all ressources always say something ...
SEJPM's user avatar
  • 46.1k