Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2010-07-18 13:03:18

calccrypto
Member
Registered: 2010-03-06
Posts: 96

What's a fast way to fulfill this condition?

given:

Choose an L-bit prime modulus p such that p–1 is a multiple of q.

what is the best way to find p that is both prime and (p-1) mod q = 0? right now, im doing the brute force way of:

q is some big prime number
p = randint(3,2^L)                     # i guess the bit size can be ignored for the moment
p = q * (1 + p/q) + 1                  # since the values are ints, p/q is really floor(p/q). this gets a value that is a (multiple of q) +1, like q = 7 ->p = 3*7 +1 = 22

while p is not prime:                  # the testing function is MillerRabin
   p = p - q

testing is taking forever, but since im terrible at reading other people's codes, ive been unable to find out how other people programed this to work very fast


Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).

Offline

#2 2010-07-18 13:11:54

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: What's a fast way to fulfill this condition?

Hi calccrypto;

A question: Is randint(a,b) that you are using a python command? If so what does it return?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#3 2010-07-18 13:18:20

calccrypto
Member
Registered: 2010-03-06
Posts: 96

Re: What's a fast way to fulfill this condition?

well the entire code block is just a pseudo code, but randint (which is also a legitimate command) is supposed to returns a random integer between a and b, inclusive. the real code is barely any different


Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).

Offline

#4 2010-07-18 13:29:11

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: What's a fast way to fulfill this condition?

Hi;

Isn't this a Rabin Miller primality tester? It has been 15 years since I have done any computerized primality testing but this reminds me of the deterministec form of Miller Rabin?!

If I am not in error then I must say this test is much slower than the probabilitic version of it. So how big are the numbers you are trying to test for primality?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#5 2010-07-18 13:43:49

calccrypto
Member
Registered: 2010-03-06
Posts: 96

Re: What's a fast way to fulfill this condition?

no. i guess my comment was a bit vague

i might as well put the real code:

	p = randint(3, 2**L)
	p = q * (1 + p/q) + 1
	while MillerRabin(p) == False:                # prime = True, composite = False
		p = p + q

miller rabin is not what im creating. rather, it is another function that im using to test my p values, and it is the probabilistic test.

the L value can be 1024,2048, or 3072


Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).

Offline

#6 2010-07-18 16:10:01

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: What's a fast way to fulfill this condition?

Hi,

2^3072 are 1000 digit numbers, maybe that's where the slow down is.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#7 2010-07-19 02:47:44

calccrypto
Member
Registered: 2010-03-06
Posts: 96

Re: What's a fast way to fulfill this condition?

yep, which is why i want to try to speed up the testing a bit


Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).

Offline

#8 2010-07-19 03:15:36

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: What's a fast way to fulfill this condition?

Hi cal;

It may not be possible with numbers that large. Those are really large.  Where is the bottleneck? Have you wrapped pieces of the code with timers to see which part is the slowest?

Also being a probabilistic primality tester each iteration reduces the probability that the number is composite by a factor of 4. So after only a couple of iterations you will have a number that is very likely to be prime. You will not have certainty.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#9 2010-07-19 06:23:27

calccrypto
Member
Registered: 2010-03-06
Posts: 96

Re: What's a fast way to fulfill this condition?

I think the bottleneck is the testing itself. Oh well. No matter. I'll eventually figure this out.

Thanks bobbym


Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).

Offline

#10 2010-07-19 06:41:05

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: What's a fast way to fulfill this condition?

Hi;

Yes, but which part is using most of the time. That's the part you try to speed up.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#11 2010-07-19 09:49:02

calccrypto
Member
Registered: 2010-03-06
Posts: 96

Re: What's a fast way to fulfill this condition?

is there a better and faster method of testing?

Last edited by calccrypto (2010-07-19 11:29:47)


Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).

Offline

#12 2010-07-19 10:57:59

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: What's a fast way to fulfill this condition?

Depends what are you trying to do? Primality testing? What?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#13 2010-07-19 11:29:20

calccrypto
Member
Registered: 2010-03-06
Posts: 96

Re: What's a fast way to fulfill this condition?

yeah. just testing if the number is prime


Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).

Offline

#14 2010-07-19 12:45:39

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: What's a fast way to fulfill this condition?

Hi cal;

You do know that the fastest deterministic test is the new one invented by those 3 Indian mathematicians and will determine the status of a number with 1000 digits in about 1 hour on a modern desktop.

This is the fastest known.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#15 2010-07-19 13:10:36

calccrypto
Member
Registered: 2010-03-06
Posts: 96

Re: What's a fast way to fulfill this condition?

darn.


Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).

Offline

#16 2010-07-19 19:35:45

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: What's a fast way to fulfill this condition?

That is the fastest for an exact answer concerning primality. If you use the probabilistic RM and run through the algorithm say 15
times you would have a probability less than .000 000 000 931 that the number is not prime.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

Board footer

Powered by FluxBB