View Full Version : Rsa Challenge

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?

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

January 18th, 2002, 12:44
Thank you

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

January 18th, 2002, 23:34
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.

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

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.

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?


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:

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

My ideas combine things from each of these methods.

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

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