So I know someone asked the same question earlier but he didn't receive an answer to the question so I am asking it again(I'm copy-pasting his code for example):
Say, for N = 90283, I compute bound =(12+(1))(ln()ln(ln$\sqrt{n}$))=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 $t^{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?