PDA

View Full Version : Rsa Challenge


int21hex
January 17th, 2002, 13:39
Does anyone know if there is a lib to deal with 178 digit integers? Intersted in trying rsa challenge and hate to start from scratch?

mike
January 18th, 2002, 01:33
Check out crypto++ at h**p://www.eskimo.com/~weidai/

int21hex
January 18th, 2002, 12:44
Thank you

mike
January 18th, 2002, 20:05
Out of curiosity, what factoring method are you going to try? Continued fraction? Quadratic sieve? Number Field Sieve?

donneo
January 18th, 2002, 23:34
hi,
IMHO, 178 digit BIGNUM is hardly to be facted within reasonable time on your individual pc.
As i know, the most popular trial approach is NFS.

int21hex
January 19th, 2002, 19:43
I am working on a different algorithm for finding the factors.... as you can imagine developing a new method is not going particularly well

mike
January 23rd, 2002, 13:35
I'd be happy to discuss it with you; I have some ideas, too. They involve factoring over prime ideals, though, and I haven't found anything that does that except PARI.

Kythen
January 23rd, 2002, 17:18
Hey guys

New factoring methods? Sounds interesting! If possible could you send me or point me to the info about what you have in mind?

Thanks!
Kythen

mike
January 24th, 2002, 14:19
The convergents x/y for the continued fraction of sqrt(n) satisfy x^2 - n y^2 < 2 sqrt(n); or in other words, x^2 mod n is small. Factor these small residues to get an exponent vector for the residue. Use linear algebra to find a set of residues whose product is a square. Then you have a set of x's whose square mod n is also a square; call it z^2. Then (x-z) divides n. About half the time you get a factor of n and the other half, x=+/-z.

See HAKMEM for more info on continued fractions.

Here's a good intro to the quadratic sieve:
h**p://www.math.ksu.edu/math511/notes/925.html

Attached is a paper by lenstra, lenstra, manasse, and pollard about the number field sieve.

My ideas combine things from each of these methods.

int21hex
January 25th, 2002, 01:59
I am trying something like this,... but i do not have the background that you do,(this is very obvious) mike (i look into the mirror and think you dam stupid newbie) but anyway i am tring to use trig of all things in three dimensions to factor... still doing research on angles... when i get some promising data from the calcs(they are taking forever) i will surely post it...wondering if there is any correlation between angles of composites composed of two prime factors

mike
January 29th, 2002, 12:07
Looks like 27 people as of today have downloaded the paper. Anyone have questions?