mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2004-01-26, 05:52   #1
chrow
 
Jun 2003

218 Posts
Question Where I find the best program to it factor keys? I use AMD.

whenever I ask to someone about as factor keys RSA, they tell me that should search NFSNET. It would like to understand because there is forum FACTORING, and NFSNET. Are not both the same thing? Do not both factor???

what I want to know same, it is what it is the fastest program to if factor a key RSA as to 640.

I want to create a program and would like have idea of how fast he should be

I never got no simple and efficient literature about sift. Not even I know what that's it. Does it anybody also know to tell where I can find something clear about that?

Apologize me for so many questions, but it is just that sane many the doubts.

As usual, apologizing me for my bad English.
it got difficult to understand something, I can try to explain of clearer form
.
.

Moises Deangelo.
lewris@ig.com.br
chrow is offline   Reply With Quote
Old 2004-01-26, 11:46   #2
BotXXX
 
BotXXX's Avatar
 
Aug 2003
Europe

2×97 Posts
Default

Both are about factoring.

But to clarify, NFSNET is a distributed computing project that focusses on factoring large numbers with the methode of GNFS or SNFS. Which stands for General Number Field Sieve or Special Number Field Sieve. More information about the NFS used in the NFSNET project you can look here: http://www.nfsnet.org/faq-nfs.html

To factor RSA640 it is hardly possible with today's computing power.

Please read the information on this page : http://www.nfsnet.org/faq-nfs.html and look at the articles that are mentioned there. It is a very exciting learning part, i think. And also read some of the information on the RSA numbers here : http://www.rsasecurity.com/rsalabs/c...ing/index.html and specially look at the reports of factoring the previous numbers. This would give an idea on hard the 640 will be with sieving.
BotXXX is offline   Reply With Quote
Old 2004-02-18, 22:51   #3
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2·331 Posts
Default

The fastest program (that I am aware of) that is able to factor RSA-640
is GNFS.
It was used to factor RSA-576.

From what I can piece together it took 8 months, using numerous computers
(100+).

It is hard to get the source code and requires a number of steps,
including one dealing with an enormous matrix greater than 5 million rows and colums.
Alot of CPU time is also needed.

The purpose of the RSA challenges is to determine the amount of time dedicated persons/teams take to factor these numbers.

The prizes are to give an incentive.

A side effect is the advancement of algorithms/programs to tackle factoring large numbers.

By writing your own code you may develop some new way to factor these numbers.
You may also find the solution just because you tried.
Pick the right search space and even a single PC could find the solution.

Nfsnet is trying to factor numbers that have special properties such as M811
2^811 - 1 using SNFS.

The team that factored RSA-576 had previously factored RSA-160,
they may be trying RSA-640, so start coding !!
dsouza123 is offline   Reply With Quote
Old 2004-02-18, 23:37   #4
Erasmus
 
Feb 2004

278 Posts
Default

Can we use NFSNET's project GUI executable for our private purposes. I think they are trying 811 bits, can i download it and use it to factor RSA-640 ???

if yes how??

if not, is there any GUI based P4 efficient program to use factoring RSA640 (without joining any server like NFSNET or PrimeNET ??)
Erasmus is offline   Reply With Quote
Old 2004-02-19, 00:20   #5
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2×331 Posts
Default

The GUI for NFSNET just is a convienent interface to the distributed linesiever.

It shouldn't be used for other purposes.

It is very involved and may be tuned for sieving M811 or at least SNFS type numbers.
It is just one step, the linear algebra step following the seiving requires substantial computing resources.

I am not aware of any P4 specific, (or other CPU specific programs) for factoring RSA-640.

Time to write one !!

At the very minimum, a program that can mod RSA-640 by prime numbers -=relatively=- close to the square root of RSA-640.
If the result is zero, you've found a factor.

Unless you pick random numbers, searching sequentially would require
a starting value that is extremely close to one of the factors or it will be
found by some team first.

Remember for primes greater than 3 they are all multiples of 6 +/- 1.

Maybe somebody will figure out some very clever way to factor large numbers.
dsouza123 is offline   Reply With Quote
Old 2004-02-19, 10:15   #6
Erasmus
 
Feb 2004

23 Posts
Default A method for RSA?????

I have been examining previous RSA challenges in recent hours. I have some preliminary ideas on RSA factorization process.

For simplicity, let D(x) denote # of digits in integer x.

RSA-576 has 193 digits. Its factors ( denote them by p and q ) are in relation
D(p) = D(q) also i think all RSA composites should follow this equality otherwise it will be easier to factor it in the long run.

Let p denote the smaller factor, q is the large one, and R is the 193 digit RSA576 composite.

I think we all agree on dealing with sqrt(R)= first. Let SR denote largest integer <= sqrt(R) for further simplicity. After finding it (a 87 digit number) , the gap between following elements should be approximated :

1) between p ( smaller factor ) and SR
2) between q ( larger one ) and SR

For RSA challenges, 1st gap is about 8,24% of SR
2nd gap is about 9% of SR

I believe, RSA composites with best efficiency ( i.e hardest case to factor any given digit composite ) should be composed of two factors with a gap of
[-/+ 8,5%] area and in addition to it, [-/+ 0,75 %] of deviation from that centered point.

Even if the conjecture above is not totally scientific, just assume it true till the end of this message.

Now, we can easily find smaller factor area center by using formula 0,85*SR and larger factor area center by 1,15*SR, It is obvious that there will be lots and lots of primes in each area since the factor of RSA576 lies on 10e87.

Here comes a choice part, there may be two kinds of approaches in my opinion which is :
1) Probabilistic approach (random selection among the factor area)
2) Sequenced approach (sieving from an initial prime to the final prime)

Both approaches will employ similar processes, first of which is declaring a pivot prime among smaller factor area. Naturally this pivot will have 87 digits.

After that selection, algorithm should find corresponding possible larger factors depending on the last digit of RSA code. The ' Last Digit Matrix ' can well represent the correspondance :

1 3 7 9 <---Last digit of q
L 1 1 3 7 9
a 3 3 9 1 7
s 7 7 1 9 3 Entries are last digit of R obviously.
t 9 9 7 3 1
Digit
of
p

After selecting the pivot, algorithm should eleminate non suitable q candidates wrt last digit check. ( It is very easy to eleminate since there is no need to calculate large integer multiplications, instead the last two bits are used )

After it is done, there will still be lots of q candidates left. The next step is to apply this procedure for last two digits of the pivot and candidates. The algorithm should somehow calculate probability of finding a suitable q among the remaining candidates after each completed step. When '[n] last digit multiplication' gets impractical and the probability becomes relatively acceptible, it should employ another sieving method which i can not figure out right now.

Probabilistic approach is like selecting a random pivot and after it is eleminated, selecting another random pivot. Since there are lots of candidates p, it may well work. Sequenced method is to start from a prime, test it, then pass to next one.

My demonstrations worked quiet well since i used MS Excel to pick primes randomly with a mean of 8,5% and stddev of 0,75% from 4 digit primes. Of course it is way too easy to work with very small primes but i think this algorithm has something to implement just for RSA challenge. By the way, i am not skilled to implement any large integer arithmetic to C, which is the only programming language i know. ( i am a university student of industrial engineering in Bogazici University, Turkey )

It may also be very silly idea that you read here, but it seemed a sensible one for me. In my opinion, the advantage of this method is we don't deal with huge numbers, instead we deal with last 'n' digits of those numbers and pray for n not to reach to high before we find acceptible candidates!!

Also i am using the following idea : since the primes are very rare in those areas (10e87) it will be very hard for selected pivot and candidate list q to construct the needed last 'n' digits of R, think of constructing 453 in last three digits of R, if some combination of p and q constructs it, it will be hard to construct it from same p and another q, it will be still possible, but it will be hard from that larger factor area!


I am waiting your critics...

Bye
Erasmus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Where can I find a Reverse and Add program? I can't find any! Stargate38 Programming 18 2015-07-10 06:08
Chance to find an n-digit factor with ECM RedGolpe Factoring 4 2007-03-23 15:24
How much ECM does it take to find a given factor? geoff Factoring 5 2004-09-29 20:14
How large a factor can P-1 testing find ? dsouza123 Software 3 2003-12-11 00:48
I want to use my own program to find.... Unregistered Software 4 2003-12-06 20:47

All times are UTC. The time now is 13:31.


Thu Dec 2 13:31:42 UTC 2021 up 132 days, 8 hrs, 0 users, load averages: 1.04, 1.16, 1.28

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.