• Announcements

Archived

This topic is now archived and is closed to further replies.

did i just break RSA?

Recommended Posts

vaneger    100
ok these two functions when combined will find the primiality of a given number in so far the fastest possible time, however i dont have a larger number library to allow it to work correctly (once the number gets too big for an unsigned long it doesnt work any more). Can some one test this code for me using a large number library and tell me how its working? Also if it works correctly with bigger numbers will this break RSA encryption?
ulong factorial(ulong n)
{
if(n<= 1)
return n;
ulong temp = n;
recurse:
temp--;
n = n * temp ;
if(temp <= 1)
return n;
else
goto recurse;
}
bool Primality(ulong n)
{
if( (factorial(n - 1) + 1) / n == 0 )
return true;
return false;
}


Share on other sites
rypyr    252
wow...um, where did you get that algorithm?

Share on other sites
vaneger    100
i designed it my self thanks

Share on other sites
CodeJunkie    144
If you don't mind me asking what is the largest prime it can test? (perhaps 11)

that's using unsigned integer

[edited by - CodeJunkie on August 13, 2003 5:52:00 PM]

Share on other sites
odizzy    122
Looks like an algorithm we learned in one of my number theory courses. Dont really remember what is was called tho

Share on other sites
Thunder_Hawk    314
I don''t think that function works correctly, unless you happen to be talking about something other than prime versus composite numbers.

Also, this line:

(factorial(n - 1) + 1) / n == 0

boils down to:

factorial(n-1)+1 < n

due to integer division. And, if I''m not mistaken, that statement is never true...

______________________________________________________________
The Phoenix shall arise from the ashes... ThunderHawk -- ¦þ
MySite
______________________________________________________________

Share on other sites
Beer Hunter    712
Your primality test (which is well known) runs in exponential time, and is therefore inferior to this.

Share on other sites
rypyr    252
quote:
Original post by vaneger
i designed it my self thanks

Sorry man, I wasn't being serious. Does this algorithm work with any prime number? Let's start with the first prime number, n=3?

if( (factorial(n - 1) + 1) / n == 0 ) :

(3-1)! + 1 = 2 + 1 = 3
3/3 != 0

doh!

Edit: Fixed my typo (forgot the minus one)

[edited by - rypyr on August 13, 2003 5:59:10 PM]

Share on other sites
CodeJunkie    144
(3-1)! = 2!

2+1 = 3
3/3 = 0

Share on other sites
Beer Hunter    712
Ah, here's what it's called:
Wilson's Theorem

EDIT: Although vaneger doesn't seem to have implemented it correctly...

[edited by - Beer Hunter on August 13, 2003 6:00:17 PM]

Share on other sites
rypyr    252
quote:
Original post by CodeJunkie
(3-1)! = 2!

2+1 = 3
3/3 = 0

What math universe do you live in?

Share on other sites
CodeJunkie    144
He can see the mistake this way....

fix with:
3/3 == 1
or
3%3 == 0

Share on other sites
Guest Anonymous Poster
quote:
Original post by rypyr
What math universe do you live in?

lol

/ == -
- == +
+ == *
* == /

maybe thats why i fail all my math classes

Share on other sites
rypyr    252
So assuming that mod change fixes it, we''re back to the original problem: This algorithm can only test numbers up to about 12 on a 32-bit machine...maybe you''ll get as far as 25 on a 64-bit machine.

Share on other sites
CodeJunkie    144
It''s the little things that kill...

Besides I think you can test to up to prime 13 before the data type overflows.(my bad)

Share on other sites
Beer Hunter    712
Improved:
bool Primality(ulong n){	ulong modfact = 1;	for (ulong i = 2; i < n; ++i)		modfact = (modfact * i) % n;	return modfact == n - 1;}

Share on other sites
CodeJunkie    144
^coolness^

Share on other sites
rypyr    252
if modfact becomes zero, you could return true immediately...

Share on other sites
CodeJunkie    144
Do you mean return False?

n=6 (not a prime)

modfact = 1
i=2; modfact = 2;(1*2)%6
i=3; modfact = 0;(2*3)%6

Yes this method is much improved. Now it can handle N somewhere up to ((2^32)^1/2)-1. (I think)

Share on other sites
vaneger    100
the algorithm works properly becasue (n-1)! + 1 is a mutiple of n thus if it is divisble by n evenly it is a prime number thus (n-1)! +1 % n == 0 is a testing case that is correct. i was posting to access the speed of the function and where to get larger number libraries to use it with alger numbers as people have stated n = 13 is highest it works for because of overflow. please dont bash me unless you know what you are talking about thank you

Share on other sites
vaneger    100
up to 13 my function appears to be slightly faster than beer hunters modified algorithm, will some one with a large number library pls test these out?

Share on other sites
Yohumbus    152
Here is a arbitrary sized integer library so you may try yourself.

http://www.swox.com/gmp/

Share on other sites
CodeJunkie    144
Run a test on both functions with N up to 65535 for correctness and speed.

I would be afraid your verison will begin to choke(huge number processing overhead) on the size of the factorials rather quickly around(n=100-200).

So please post back with the results.

Share on other sites
KalvinB    102
Well. You WOULD have broken RSA except for the fact you used a goto. And because of that, you fail.

while (temp>1)
{
temp--;
n = n * temp ;
}
return n;

Ben

[ IcarusIndie.com | recycledrussianbrides.com ]