Need help in factoring algorithms

Rsa200, The 200 digit RSA challenge no is factored on may 9.

The German researchers, RSA has reformulated its challenge and now expresses numbers in bits (base 2) instead of decimal (base 10)





source

http://news.com.com/2061-10789_3-5702146.html
 
Last edited:

Zurtex

Science Advisor
Homework Helper
1,120
1
So what's the problem?
 

Zurtex

Science Advisor
Homework Helper
1,120
1
I'm still confused, it's just the same number with separators every 3 digits...
 

saltydog

Science Advisor
Homework Helper
1,582
2
Zurtex said:
I'm still confused, it's just the same number with separators every 3 digits...

Yea right. And because of that I would ask aravindsubramanian to kindly prepare a short report detailing how RSA-200 was factored. Include the technique used, how long it took, what kind of computer resources were used, and what criteria was used in selecting the two primes in it's product. :smile: Or just ignore me. :yuck:
 

saltydog

Science Advisor
Homework Helper
1,582
2
saltydog said:
Yea right. And because of that I would ask aravindsubramanian to kindly prepare a short report detailing how RSA-200 was factored. Include the technique used, how long it took, what kind of computer resources were used, and what criteria was used in selecting the two primes in it's product. :smile: Or just ignore me. :yuck:
Aravindsubramanian, in case you're not already annoyed by me, here's two more:

Download the two prime factors in Mathematica and verify they work. You'll find out quick-like why you dont want any commas in there.

Finally, how do you check that these large numbers are in fact prime? . . . "why don't you Salty?". Suppose I could. Think one way has to do with Fermat's little theorem. Need to check . . .

Edit: Oh yea, I don't think they even need to be prime, just relatively prime. Huh Zurtex?
 
Last edited:

Zurtex

Science Advisor
Homework Helper
1,120
1
saltydog said:
Finally, how do you check that these large numbers are in fact prime? . . . "why don't you Salty?". Suppose I could. Think one way has to do with Fermat's little theorem. Need to check . . .

Edit: Oh yea, I don't think they even need to be prime, just relatively prime. Huh Zurtex?
Fermat’s little Theorem is alright, but I'd rather go with the Miller Rabin Test, in my number theory course we integrated the two tests in to a single program for the minimum amount of run time needed to work out if the number is a prime to a certain level of probability.

Where n is the number I was fairly happy to reduce the probability of the number being not being prime down to less than 1/n which took a run time of about:
[tex]\text{O} \left( \frac{1}{\sqrt{2}} \left( \log n \right)^{2} \right)[/tex]

Which was very useful as you can imagine.
 
Last edited:

saltydog

Science Advisor
Homework Helper
1,582
2
Here's the Miller-Rabin test:

Let n be an odd prime and write:

[tex](n-1)=d2^s[/tex]

That is, remove all the s factors of 2.

Then one of the following must be true for some a[itex]\in[/itex][1,n-1]:

[tex]a^d\equiv 1(\bmod n)[/tex]

or, letting:

[tex]k=d2^r[/tex]

[tex]a^{k}\equiv -1(\bmod n)\quad\text{for some}\quad 0\leq r\leq (s-1)[/tex]

So I wrote the Mathematica code below to implement this test (not shown is the routine to get s and d). It actually checks for composite by running through a total of amax trials, and all the values of r if the first test is not satisfied and if none are found, then judges the number to be composite. I checked the two prime factors of RSA-200. What I found interesting was the small number of factors of 2 in (n-1). The first prime had (in n-1), a single factor of 2 and the second had only two factors of 2.

Is this a characteristic feature of RSA primes?

Code:
MillerRabin[pval_, amax_] := Module[{a, s, d, r, aval, rsum, aexp},
      (* get d and s for test *)
      plist = GetSandD[pval];
      s = plist[[1]];
      d = plist[[2]];
      For[a = 1, a <= amax, a++,
        aval = Random[Integer, {1, pval - 1}];
        If[PowerMod[aval, d, pval] != 1,
          rsum = 0;
          For[r = 0, r <= s - 1, r++,
            aexp = d(2^r);
            If[PowerMod[aval, aexp, pval] != pval - 1,
              rsum += 1;
              ];
            ];
          If[rsum == s,
            Return["composite"];
            ];
          ];
        ];
      Return["possible prime"];
      ];
 

Zurtex

Science Advisor
Homework Helper
1,120
1
RSA-200 is a really old number so yeah they are likely to have designed it such that it was a bit harder to factor by such methods.

The newer RSA numbers on the other hand have been made when the best methods available to attack such numbers are not bias to any particular type of numbers so I doubt they will have been made quite the same way.
 
Hai saltydog,

Rsa200 was factored using general number field sieve factoring agorithm.Sieving starts on christmas2003. The initial "sieving" step took the equivalent of 55 CPU-years on a single machine (2.2Ghz Opteron CPU).

see
http://en.wikinews.org/wiki/200_digit_number_factored


for more information

For primality testing we can use AKS primality testing algorithm.This is the only polynominal time algorithm available for primality testing.
 
Last edited:
644
1
aravindsubramanian said:
For primality testing we can use AKS primality testing algorithm.This is the only polynominal time algorithm available for primality testing.
Umm correction(!), it is the only "deterministic" polynomial time algorithm available for primality testing [edit]till Riemann Hypothesis is proved true[/edit]. Otherwise we did have probabilistic algorithms earlier which worked in polynomial time.

-- AI
 
Last edited:

saltydog

Science Advisor
Homework Helper
1,582
2
Assuming the truth of the generalized Riemann Hypothesis, if all values of a up to [itex]2 (ln n)^2 [/itex] are tested in the M-R test, then it becomes deterministic with a run-time of [itex]O(ln n)^4[/tex]
 

saltydog

Science Advisor
Homework Helper
1,582
2
aravindsubramanian said:
Hai saltydog,

Rsa200 was factored using general number field sieve factoring agorithm.Sieving starts on christmas2003. The initial "sieving" step took the equivalent of 55 CPU-years on a single machine (2.2Ghz Opteron CPU).

see
http://en.wikinews.org/wiki/200_digit_number_factored


for more information

For primality testing we can use AKS primality testing algorithm.This is the only polynominal time algorithm available for primality testing.
Hello Aravind, just suggestions. Probably knew it already huh? I noticed your thread on RSA. What's the largest primes you've ever used in an RSA encryption from scratch? I used two 266-digit primes to encrypt a treasure map once. Yea, you didn't know I was a pirate did you? :smile:

Oh yea, here it is: :smile:

584565320456079056472406794697025571766693520913877507241662721424514015287011603416154188536836341015926767446223936487086729380578563273429545303354882999335872814693052640028188293170276069519193534066874924002823402299557574111508994858974296221386784608393260544702126406796897098959631948264896983143307205839708632666773260086979553742525654915079519938492366869933223381055342706622
425031839180665648719174085014618369417651996764817708423914215175891883694441939466211544062220527814839790244648360067898947829169131086041
 
Last edited:
644
1
saltydog said:
Assuming the truth of the generalized Riemann Hypothesis, if all values of a up to [itex]2 (ln n)^2 [/itex] are tested in the M-R test, then it becomes deterministic with a run-time of [itex]O(ln n)^4[/tex]
Post edited :rolleyes: :tongue:

-- AI
 

Related Threads for: Need help in factoring algorithms

  • Posted
Replies
9
Views
6K
  • Posted
2 3
Replies
52
Views
8K
  • Posted
Replies
3
Views
2K
Replies
11
Views
3K
Replies
1
Views
2K
  • Posted
Replies
2
Views
1K
Replies
10
Views
5K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top