Own Project / Commercial License

[friedo]

Hello.

We plan to factorize large primes (150 Digits and more) in an own commercial Project. Therefore i am searching for "fire and forget" software solutions for distributed factoring specially using windows clients and one server script (php etc.) like nfsnet for example.

Is there any "commercial" software on the market or sw which could be licensed commercially without big adaptions for running in an distributed environment?

Can anyone tell me who is responsible for the nfsnet-client and server scripts to ask for commercial licensing?

Best regards,
friedo

[alpertron]

Originally Posted by friedo

Hello.

We plan to factorize large primes (150 Digits and more) in an own commercial Project. Therefore i am searching for "fire and forget" software solutions for distributed factoring specially using windows clients and one server script (php etc.) like nfsnet for example.

...or more exactly 155 digits (RSA-512). If this is what you mean, forget it.

[VJS]

This sounds like I great idea for a start up, I think you should really start with trial division software. There is quite a bit of software out there just look around, but the best bet for your company would be to write your own in java.

Take the number divide by some unknown randomly generated number... repeat, could be a small program.

Goodluck

[Mystwalker]

Or ask the guys at primegrid.com - they even factorize a 193-digit RSA number at the moment.

[akruppa]

Originally Posted by VJS

Take the number divide by some unknown randomly generated number... repeat, could be a small program.

Goodluck

But do a probable primality test on the random numbers first. No point in trying to test composites as factors, because you are looking for the prime factors!

Glad to help,

Alex

[xilman]

Originally Posted by akruppa

But do a probable primality test on the random numbers first. No point in trying to test composites as factors, because you are looking for the prime factors!

Glad to help,

Alex

Alternatively, you could use Fermat's factoring algorithm. It is very easy to program and the innermost loop runs extremely quickly because multiple precision division isn't required.

Even better, Fermat's algorithm is especially efficient when the two factors are close together. Given that most RSA public moduli have the same number of bits, they are inevitably much easier to factor by Fermat's method than are general numbers of the same size.


If you'd like pointers to how Fermat's method works, just ask. It's in Knuth, for instance.


Paul

[Uncwilly]

Originally Posted by friedo

We plan to factorize large primes (150 Digits and more) in an own commercial Project.

You can't factor prime numbers. You can factor a composite that is made of primes that are ~150 digits long.

[fetofs]

Originally Posted by xilman

Alternatively, you could use Fermat's factoring algorithm. It is very easy to program and the innermost loop runs extremely quickly because multiple precision division isn't required.

Is there a ceil() equivalent in GMP?

[dsouza123]

Which Fermat method ?

After analysis and experimentation with the Fermat method using only
addition/subtraction and test for zero/equality,
for larger numbers, for example a 300 digit number which has as factors
two 150 digit primes, it would take a lifetime to get to the second number
that could be part of the solution.

It is far worse than just dividing by odd positive integers of the correct size.
They could be consecutive odds or consecutive odds but skipping 1 out of 3
or random odds.
Also a probable primality test on the odd positive integer may require more
time then just doing the division, and you still wont know if it is a factor
of the number in question.
I haven't done any tests to determine how many divisions per second
are possible on a fast PC.

The Fermat method that effectively tests consecutive squares minus
the number in question for a square, using only additions and squareroot,
for a 300 digit number, can evaluate over half a million per second on a fast PC.

Whether either trial division or the faster Fermat method will find a factor
in a lifetime would mainly depend on testing very near the solution because
even with millions of PCs the search space is enormous.
In the very highly unlikely event that you test extremely near the solution,
either method could find a solution in minutes or hours.
The most likely outcome is never to find a solution in a lifetime.

That is why NFS and similar algorithms are used instead,
with hundreds/thousand of PCs and a few years calculation time
a solution can be found for 300 digit numbers (that have as factors
two primes of equal size).

[Phil MjX]

Originally Posted by VJS

This sounds like I great idea for a start up, I think you should really start with trial division software. There is quite a bit of software out there just look around, but the best bet for your company would be to write your own in java.

Take the number divide by some unknown randomly generated number... repeat, could be a small program.

Goodluck

Analyzing the computer chess programs and especially the way they play finals with tablebases, you may realize that there is a better way to factorize RSA512 numbers : precompute all the 256 bits prime, store them on HD (using a hashing system may help) and simply read the tables to find the appropriate factor...
You can also sell the DVD's containing this "factor tables" and pay off the investment !!!

Philippe.

PS : a first optimization : as in the how-to-win-lottery-systems, you can omit in your tables potential candidates that are very "improbable", as those with ten "1" on a row, or containing many more "0" than "1" and so...

[Patrick123]

One method that I played around with was along these lines. Primary School Maths.

procedure factor (a,b: string; Count: integer);
var
...sx, sy, t: string;
...x, y, integer;

for x := 0 to 9 do begin
..sx := IntToStr(x) + a;
..if pattern(sx) then continue;
..if TestNum Mod StrToInt(sx) = 0 then begin
.....Print sx;
.....exit;
..end;

..for y := 0 to 9 do begin
.......sy := IntToStr(y) + b;
.......if pattern(sy) then continue;
.......if TestNum Mod StrToInt(sy) = 0 then begin
..........Print sy;
..........exit;
.......end;
.......t := IntToStr( TestNum - StrToInt(sx) * StrToInt(sy))
.......if StrToInt(t) < 0 then break;
.......if Number_of_Zeros_at_End(t) >= Count then
.........factor(sx,sy,Count+1);
..end;
end;

The pattern function filters out numbers like 11111001 etc.
This would of course eliminate billions of numbers at a time thus the larger the number, the more efficient it becomes.

Regards
Patrick