Mathematica 9 is now available
Student Support Forum
-----
Student Support Forum: 'quadratic sieve help' topicStudent Support Forum > General > "quadratic sieve help"

Next Comment >Help | Reply To Topic
Author Comment/Response
jt
12/11/05 4:31pm

Hi, I am trying to write a Mathematica program for the quadratic sieve, but I am not that fluent in Mathematica. I need to factor this number:
n = 11903187221057911

I have a factor base of size 50:

{2, 3, 5, 7, 11, 13, 19, 37, 53, 59, 67, 71, 73, 89, 101, 103, 107, 127, 131, 137, 149, 151, 163, 173, 181, 193, 223, 227, 233, 251, 263, 269, 277, 281,
293, 307, 313, 317, 353, 359, 373, 383, 389, 397, 401, 421, 431, 433, 439, 457}

that I have found for my number n. Also I have found the Tonelli's numbers for these primes in the factor base to be:

{1, 1, 1, 3, 3, 5, 8, 12, 22, 8, 5, 27, 3, 10, 37, 12, 37, 63, 49, 61, 29, 64, 65, 8, 43, 53, 109, 17, 59, 78, 83, 29, 72, 79, 36, 28, 50, 25, 93, 139, 48, 89, 58, 163, 198, 204, 174, 24, 154, 122}

Now, I must choose a Sieving Interval I = [-M,M] which I suppose I can take anything? So I take:
M = 32

Now I'm at the sieving part I think. I have to find out how to record the divisibility of each g(r(i)) = r(i)^2-n, where r(i) = Floor[sqrt[n]]-M+i; where i goes from 1 to 2M = 64, by each prime in the factor base.

How would I make the matrix and then add Floor[1/2 +log p] to the (i,j) entry if r(i) is congruent to + or - the tonelli number t_p (mod p(j))

I am stuck at this part described above.

I know that I have to factor the r(i)'s into the prime factorizations and compare that to my factor base to see if the r(i) is completely factored by primes in my factor base but I don't know how to code this in Mathematica or even where to start.

I tried to use the built in function FactorInteger[n] which gives me the prime factorization and the powers but I am unable to split the value that the function gives me (It seems that it may be just giving me one value instead of components that I could use are variable values) for example: FactorInteger[50] gives me {{2,1},{5,2}} to give 2*25 = 50.

After all this I know I have to do gaussian elimination and I think I can use rowreduce mathematica function but im not sure.

Please help if you can. Thanks.



URL: ,

Subject (listing for 'quadratic sieve help')
Author Date Posted
quadratic sieve help jt 12/11/05 4:31pm
Re: quadratic sieve help David 03/29/13 11:50am
Next Comment >Help | Reply To Topic