1
$\begingroup$

So I am at the same step as someone from math.stackexchange but he never recieved an answer so I will copy-paste his question here:

Say, for N = 90283, I compute bound 𝐡=𝑒(12+π‘œ(1))(ln(𝑛)ln(lnπ‘›βˆš))=44, where I take π‘œ(1)=0.22 (just a random guess, I assume). What is the best way to pick good π‘œ(1)?

Then I take 𝐢=⌈$\sqrt{n}$βŒ‰=301

Then using Sieve of Eratosthenes I get a list of primes < 𝐡:

{2,3,5,7,11,13,17,19,23,29,31,37,41,43}

Then by computing Jabobi (Legendre) symbol for each value in the primes list, I pick the first quadratic nonresidues to get factor base: {2,3,7,17,23,29,37,41}

Then using the Tonelli-Shanks algorithm I compute modular roots ±𝑑, where 𝑑 is a solution to 𝑑$^{2}$ ≑ 𝑁 (mod 𝑝) with 𝑝 a prime form factor base.

Then I get two arrays of solutions π‘ π‘œπ‘™1 = π‘‘βˆ’πΆ (mod 𝑝) and π‘ π‘œπ‘™2 = βˆ’π‘‘βˆ’πΆ (mod 𝑝), with p's from factor base. and also get one arrays of logarithms for p's 𝑙𝑝 = ln𝑝 rounded up to some precision, say two decimal digits. What is a good precision?

sol1 ={0,0,2,13,11,26,10,28}

sol2 ={0,1,5,14,8,10,17,26}

𝑙𝑝 ={0.69,1.1,1.95,2.83,3.14,3.37,3.61,3.71}

Now as far as I understand I have to initialize 'sieving_array' initialized to 0's, say, to size = 60 elements. Also, how should I choose size of the sieving interval? Is there any formula similar to the bound?

Then I have to add values from 𝑙𝑝 to sieving array to positions π‘ π‘œπ‘™1[𝑗]+π‘–βˆ—factor_base[j] and π‘ π‘œπ‘™1[𝑗]+π‘–βˆ— factor_base[j], where 0≀𝑖≀ size and 0≀𝑗≀|factor_base|. And for prime 𝑝=2 add 𝑙𝑝 only to positions with sol1. So I get this list (rounded to two decimal digits):

SieveArray ={1.79,1.1,2.64,1.1,1.79,1.95,1.79,1.1,3.83,3.05,8.77,3.14,3.74,3.93,3.52,1.1,3.74,3.61,1.79,3.05,0.69,1.1,1.79,1.95,1.79,1.1,9.72,1.1,5.5,0.0,6.57,7.07,0.69,3.05,4.93,0.0,1.79,3.05,0.69,4.47,3.74,0.0,1.79,1.1,2.64,1.1,1.79,8.39,4.62,1.1,0.69,3.05,1.79,0.0,10.49,4.47,0.69,4.24,3.74,0.0}

Now I am confused. The next step is(in Contini's paper) is to check each value is log(2x$\sqrt{n}$) but I don't get what x is. Also can someone please explain how to calculate the size and Sieving Interval?

$\endgroup$
  • 1
    $\begingroup$ Welcome to crypto.SE. Notice that we tend to use MathJax for formulas. Comments: $N=90283$ is very small for QS. Actual implementations for integers of crypto interest (hundreds of bits) often are RAM-bound, and make sieving_array as large as available RAM allows, with entries only 1 byte or perhaps 2, rarely 4, again to conserve RAM. $\endgroup$ – fgrieu Jan 17 at 17:27
  • $\begingroup$ This means the scaling of log should be such that the sum expected in each entry does not overflow (at least, not for sum below the smoothness bound selected). That's what determine scaling of log, and it is absolutely essential to first decide how many bytes per entry you use. What about reading section 6 in Richard Crandall & Carl Pomerance's Prime Numbers, A Computational Perspective, Second Edition? $\endgroup$ – fgrieu Jan 17 at 17:51
  • $\begingroup$ Does Prime Numbers, A Computational Perspective, teach all of this? $\endgroup$ – aayush Lak Jan 17 at 23:51
  • $\begingroup$ Yes, it does, though it assumes some pre-existing degree of fluency with computer programming. The first link in this Google query might get you an abstract of some relevant text. $\endgroup$ – fgrieu Jan 18 at 10:07
  • $\begingroup$ Can you explain to me what he is doing in more detail, please? Maybe with an example of a small sieve? It would be really helpful as he didn't give any example sieve or factorization. Thanks. $\endgroup$ – aayush Lak Jan 18 at 20:25

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.