Archived

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

did i just break RSA?

This topic is 5238 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites