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?

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.

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

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.

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?

Powered by vBulletin® Version 4.2.2 Copyright © 2020 vBulletin Solutions, Inc. All rights reserved.