hi all

i have a homework for Lehmann primality test and i have to know very big numbers as big as x**(2**128)

python is enough for 2**128 but when numbers bigger than it don't do it

my teacher python has a structure for it and i didn't find it for 2 days

thanks

Recommended Answers

All 6 Replies

decimal module has suppport of very long and accurate numbers, but I am not sure if it is enough for such extreme case. Usually you can find ways to work on powers with modulo, standard python pow supports second argument for modulo.

def mod_al(p,a):
	r=1
	c=(p-1)/2
	i=1
	while i<c+1:
		r=(r*a) %p
		i=i+1
	return r


p=input("give me number\n")
a=2
mod=mod_al(p,a)

if mod==1 or mod==p-1:
	print "this number can be prime"
else:
	print "this number don't prime"

this is my program maybe you can find a solution
it works but when numbers very big such as 2**50 it don't

2**218 = 421249166674228746791672110734681729275580381602196445017243910144 and
2**50 = 1125899906842624
Either one is going to take a long time. As Tony said you should be using the decimal module.

this is my program maybe you can find a solution
it works but when numbers very big such as 2**50 it don't

Not unless there is a mind reader here who can intuit what "it don't" means. I don't think any one is going to waste hours running the code through bigger and bigger numbers until they find out what "it don't" means.

Search for "prime number python" on DaniWeb; the site has a number of posts and snippets concerning primality testers. I specifically remember one which is useful for very large numbers, but it is probablistic: http://www.daniweb.com/software-development/python/threads/334159 (Look for vegaseat's answer at the end). Also a healthy google search on prime numbers should prove helpful.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.