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

You are not logged in. #1 20100719 11:03:18
What's a fast way to fulfill this condition?given:
what is the best way to find p that is both prime and (p1) mod q = 0? right now, im doing the brute force way of: Code: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). #2 20100719 11:11:54
Re: What's a fast way to fulfill this condition?Hi calccrypto; In mathematics, you don't understand things. You just get used to them. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof. #3 20100719 11:18:20
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). #4 20100719 11:29:11
Re: What's a fast way to fulfill this condition?Hi; In mathematics, you don't understand things. You just get used to them. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof. #5 20100719 11:43:49
Re: What's a fast way to fulfill this condition?no. i guess my comment was a bit vague 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. Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated). #6 20100719 14:10:01
Re: What's a fast way to fulfill this condition?Hi, In mathematics, you don't understand things. You just get used to them. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof. #7 20100720 00:47:44
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). #8 20100720 01:15:36
Re: What's a fast way to fulfill this condition?Hi cal; In mathematics, you don't understand things. You just get used to them. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof. #9 20100720 04:23:27
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. Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated). #10 20100720 04:41:05
Re: What's a fast way to fulfill this condition?Hi; In mathematics, you don't understand things. You just get used to them. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof. #11 20100720 07:49:02
Re: What's a fast way to fulfill this condition?is there a better and faster method of testing? Last edited by calccrypto (20100720 09:29:47) Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated). #12 20100720 08:57:59
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. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof. #13 20100720 09:29:20
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). #14 20100720 10:45:39
Re: What's a fast way to fulfill this condition?Hi cal; In mathematics, you don't understand things. You just get used to them. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof. #15 20100720 11:10:36
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). #16 20100720 17:35:45
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 In mathematics, you don't understand things. You just get used to them. I have the result, but I do not yet know how to get it. All physicists, and a good many quite respectable mathematicians are contemptuous about proof. 