Finding primitive roots using python

[wrong_class]

Im not sure if this should go in the math/number theory section or here, but here it goes:

how do programs calculate the primitive roots mod n of extremely large primes? My program will only go up to 12-14 bits before having memory errors caused by storage of the totient of the prime number

does anyone have any code that i can integrate into my program? pseudocode? general idea that can be easily translated into code? anything?

THIS IS NOT HOMEWORK. WRITING MATH PROGRAMS IS A HOBBY, NOT AN ASSIGNMENT

 

[story645]

how do programs calculate the primitive roots mod n of extremely large primes?

It depends on the library your using, but probably the way it's described in the wiki article.

Can I see the code you're using?
As a quick fix for memory errors, I try to optimize my code so that as much of the math as possible is done in place 'cause python's memory management is kind of lousy.

Are you using numpy and scipy (which push a lot of the heavy number crunching to C++ and fortran) and what kind of machine are you using? I do some fairly large number crunching with numpy/scipy and can usually push it pretty far before it croaks.

 

[wrong_class]

Im not using any library at all. I like to write programs with as few outside sources as possible.

my code is currently:

def prim_root(value):
	# `tot` gets the list of values coprime to the input, 
        # so len(tot()) is the correct totient value
	totient = tot(value)
	roots = []
	exp = len(totient)
	for x in totient:
		y = 1
		while pow(x, y, value) != 1:# i forget exactly why i did this
			y += 1              # i think it was because of the 
		if y == exp:                # period of the mod value
			roots += [x]
	return roots

i had a code that only tested prime numbers, using the carmichael == totient test, but it turns out this code is faster

im using a lenovo t410 laptop

 

[story645]

Im not using any library at all. I like to write programs with as few outside sources as possible.

*headdesk* It's really important to pick up enough software skills to be able to write your own code, but it's just as critical to be able to use other peoples code. Numpy & Scipy are optimized for numerical calculations and therefore may handle your numbers better.

Can I see tot and pow? I'm wondering if the problem may be in either of them.

random, but why aren't you doing roots.append(x)?

My program will only go up to 12-14 bits before having memory errors caused by storage of the totient of the prime number

which line does your code crash at?

im using a lenovo t410 laptop

how much ram?

 

[wrong_class]

def gcd(a, b):
	a, b = max(a, b), min(a, b)
	c = 1
	while c:
		c = a % b
		a = b
		b = c
	return a

def tot(n):
	phi = []
	x = 1
	while x < n:# not for x in xrange(n) because the input is too big for xrange
		if gcd(x, n) == 1:
			phi += [x]
		x += 1
	return phi

pow is the built in command: pow(a,b,c) -> a**b mod c

is .append() faster/otherwise better than +=? if so, i'll change it.

ok. the code errors in 'tot': "phi += [x]' due to memory errors. the 'phi' list simply got too big

and the laptop has 4gb ram, with and idle load of about 1.5 gb. right now, its using 2.85 gb

go you know of any mathematical tricks to get at least some of the generators? the wiki article sort of has one, but it involves the factoring problem, making it only theoretical

 

[story645]

is .append() faster/otherwise better than +=? if so, i'll change it.

For some implementations, but it probably won't make a difference. It's just the common way to do it.

the code errors in 'tot': "phi += [x]' due to memory errors. the 'phi' list simply got too big

This is going to throw in some latency, but what about writing phi out to disk as you generate it? And then pulling in the numbers one by one as you calculate your factors? That way it's never all stored in memory? If you save it out as a numpy array, you can take advantage of slicing thereby keeping the pointer to the file open the entire time.

How big does phi get? Are you working with Int16? Int32? Int64? and how many numbers? The biggest phi could possibly get before crashing is the size of whatever your free memory+page space is.

 

[wrong_class]

[STRIKE]hm... you gave me an idea...since i don't need the actual list, i'll calculate the actual totient value, rather than the set that makes them up.[/STRIKE] i do need the list, which is a problem

im using values up to 2048 bits. since the values I am getting are changed so that they become the closest prime, the 'tot' list gets quite big

 

[story645]

i do need the list, which is a problem

You actually don't. It'll make your code take longer, but you can build totient on the fly since all the phi calculations are done on each element of totient. You just substitute the for loop for the while loop and do everything else nested.

im using values up to 2048 bits.

That's Int256, meaning you probably don't even want to save totient to file as your data set is going to be massive.

 

[wrong_class]

can you show me? I am not seeing it. I didnt put this in, but later on, I am going to be choosing a random value from the primitive roots to use for calculations

 

[story645]

roughly:

x = 1
roots = []
while x < n:
        if gcd(x, n) == 1:
                y = 1
	        while pow(x, y, value) != 1
	                y += 1              
		        if y == exp:               
			        roots += [x]
        x += 1

but since roots will also probably blow up, you should probably dump roots to file as you write it