Archived

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

vaneger

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


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

[edit]
that's using unsigned integer

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

Share this post


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


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


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


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


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


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


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


Link to post
Share on other sites
vaneger    100
well it would appear this is the fastest possible way to find prime numbers , if you can find a number library that will work with it.

Share this post


Link to post
Share on other sites