NFS sqrt by hand

[debrouxl]

Once I understand how it works I would like to attempt to make an example nfs factorization for mersennewiki.

Good idea


I see you're mentioning your TI-89T: the TI-Z80/TI-68k community used results from the factoring community to factor TI's public RSA signing keys, so it would be funny to have an implementation of NFS (with small factor bases, obviously), and maybe parts of the post-processing, running (between others) on the TI-68k platform

For the uninitiated: TI-68k calculators have had, for the past ten years, a 68000 clocked at ~12 MHz, 256 KB of RAM and 2 (89 / 92+) or 4 MB (V200 / 89T) of Flash memory.
With TI's Advanced Mathematics Software OS, < 192 KB of RAM and ~640 KB (89/92+) or 2.5 MB (V200/89T) of Flash are available to users, maximum block sizes for both RAM and Flash are a bit below 64 KB.
PedroM, an alternative GPL'ed OS with better POSIX support, leaves more RAM and Flash memory available to the user, and IIRC, at least one of the maximum block sizes is higher than with AMS.

[henryzz]

While working out the QCB I came across this problem. I have left the book which is my other source at school so I can't reference it until monday.

Originally Posted by paper jasonp linked to

For each element (p,r) in the QCB store a 1 if the Legendre symbol

=1 else a 0

I assume by "1 else a 0" he means if the legendre symbol is -1.
Also Legendre symbols are only defined if the bottom number is a prime which r often isn't. Does he mean jacobi symbol?

[henryzz]

Originally Posted by debrouxl

I see you're mentioning your TI-89T: the TI-Z80/TI-68k community used results from the factoring community to factor TI's public RSA signing keys, so it would be funny to have an implementation of NFS (with small factor bases, obviously), and maybe parts of the post-processing, running (between others) on the TI-68k platform

I might implement NFS on my TI-89T one day although it might be in the distant future as TI-BASIC is a bit slow(sieving not tf might be fast enough dunno) and I don't know 68k yet. Schoolwork is stopping me from spending much time on anything currently.

[jasonp]

Originally Posted by henryzz

I assume by "1 else a 0" he means if the legendre symbol is -1.
Also Legendre symbols are only defined if the bottom number is a prime which r often isn't. Does he mean jacobi symbol?

I think you have to switch p and r; you plug the r into the relation and take the legendre symbol with p.

Note that quadratic characters are not a requirement for NFS, they only help make sure that the algebraic product you compute has a square root in the underlying number field. If your sample problem is small enough you can search for the square root by brute force and just use another dependency if you don't find one. For larger problems, you essentially will never find a square root if you don't use them.

[henryzz]

Originally Posted by jasonp

I think you have to switch p and r; you plug the r into the relation and take the legendre symbol with p.

Note that quadratic characters are not a requirement for NFS, they only help make sure that the algebraic product you compute has a square root in the underlying number field. If your sample problem is small enough you can search for the square root by brute force and just use another dependency if you don't find one. For larger problems, you essentially will never find a square root if you don't use them.

So my previous dependecies might have been fine. I had two with 8 relations in it not an odd number. I would rather not have to do the guassian again by hand.

Originally Posted by jasonp

Actually, looking it up I think we're both right (though it's not for the reason above). If

- the algebraic polynomial (of degree d) has a leading coefficient A_d > 1

- the rational polynomial has a leading coefficient R_1 > 1

then you have to multiply rat_sqrt by A_d^(d-2+S/2) mod N and multiply alg_sqrt by R_1^(S/2) mod N, where S is the number of relations in the dependency (if you use free relations, the exponent in the first term has the number of free relations in the dependency subtracted out...it sucked having to figure that out myself). S odd is not allowed in that case, but when both leading coefficients are 1 then you can have an odd number of relations in the dependency.

Does this mean for my poly I can use an odd number of relations? Would that make it harder? If so I might be able to use the 5 above.

[Random Poster]

Originally Posted by jasonp

For larger problems, you essentially will never find a square root if you don't use them.

Unless you find the generators of the ideals and the unit group, and write the algebraic side of each relation as a product of these generators. Of course that won't work with GNFS, but it might be possible with quite large SNFS jobs.

[R.D. Silverman]

Originally Posted by Random Poster

Unless you find the generators of the ideals and the unit group, and write the algebraic side of each relation as a product of these generators. Of course that won't work with GNFS, but it might be possible with quite large SNFS jobs.

In fact, before the invention of the use of quadratic characters, this
is exactly what we used to do.

[jasonp]

Originally Posted by Random Poster

Unless you find the generators of the ideals and the unit group, and write the algebraic side of each relation as a product of these generators.

Yes, I'd forgotten about that. It still amazes me that a single algorithm with a few bells and whistles can deal with any number field problems that can cause failure, with high probability.

Henry: yes, your polynomials are simple enough that you can use an odd number of relations. You may still need to use quadratic character tests; the Gauss elimination code in the QS implementation I mailed you can handle matrix dimensions into the thousands pretty easily.