tag:blogger.com,1999:blog-3722233.post4676602153168845040..comments2024-07-19T08:15:14.879-05:00Comments on Computational Complexity: Finding PrimesLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger18125tag:blogger.com,1999:blog-3722233.post-30159496403249635912016-03-10T14:18:03.368-06:002016-03-10T14:18:03.368-06:00Not sure if this has been done before?
Solving f...Not sure if this has been done before? <br /><br />Solving for primes without division<br /><br />It begins with the only true prime pair 2 and 3, whose product forms the magical composite number 6. All other primes orbit around it and its multiples. Using alternating patterns of 2 and 4, the composites are revealed in succession beginning with 5 in the first segregated pair of the series. Each integer in the series is raised to the second power and then its product of 2 and 4 reveals the distribution of the composite numbers. As the process is repeated, the order that 2 and 4 are used to generate the products alternates, to progressively strip away the remaining composites integers and reveal the rest of the primes. <br /><br />I have written some simple code in Python to demonstrate that it works. It can be seen here https://github.com/Tusk-Bilasimo/Prime-Sive/blob/master/Prime%20Code%2001.pyAdrian Suttonhttps://www.blogger.com/profile/17061814359414678404noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17331261221552517192009-08-08T09:10:22.867-05:002009-08-08T09:10:22.867-05:00I added a link to a 2006 post on full derandomizat...I added a <a href="http://blog.computationalcomplexity.org/2006/07/full-derandomization.html" rel="nofollow">link</a> to a 2006 post on full derandomization.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82044057895005783172009-08-08T04:37:55.162-05:002009-08-08T04:37:55.162-05:00"If you you either believe in full derandomiz..."If you you either believe in full derandomization"<br /><br />I do not think there is a formal way to define "full derandomization" (and certainly I have no idea how to do it) but it can refer to a meta conjecture that every randomized construction/algorithm related to "interesting" mathematics can be replaced by a deterministic constriction/algorithm (with a polynomial overhead). <br /><br />In this particular case "derandomization" essentially refer to "random-like" properties of the primesGilhttp://gilkalai.wordpress.com/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39285062108196368702009-08-07T07:16:53.621-05:002009-08-07T07:16:53.621-05:00"A deterministic algorithm exists if you eith..."A deterministic algorithm exists if you either believe in full derandomization or in conjectures on distributions of primes."<br /><br />Dear Lance, what do you mean by "full derandomization"? Is there a conjecture (no matter how bold; but not obviously false) regarding derandomization that will imply that there is a deterministic algorithm to find large primes?Gil kalaihttp://gilkalai.wordpress.com/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-981381420910910392009-08-05T23:14:29.747-05:002009-08-05T23:14:29.747-05:00In terms of practical efficiency I recall that the...In terms of practical efficiency I recall that the superpolynomial algorithm of Cohen and Lenstra used only 4 Rabin-Miller tests because they weeded out most composites the expected benefit of additional R-M tests was so small relative to the superpolynomial part which involved the hard-coded products of the first n primes...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46451025125067016662009-08-04T17:13:50.364-05:002009-08-04T17:13:50.364-05:00The last two sentences are misleading. The algorit...The last two sentences are misleading. The algorithm to find a prime, given an input, is deterministic. The inputs need not be generated deterministically. The whole point of crypt is to choose inputs that the adversary would have little chance in guessing (or finding given certain information).<br /><br />On a related note, Hendrik Lenstra gives a great talk on the difference between testing for primality and factoring for both integers and polynomials.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90639216305369663552009-08-04T15:48:21.745-05:002009-08-04T15:48:21.745-05:00Ok I misunderstood and thought that if there is a ...Ok I misunderstood and thought that if there is a deterministic algo to find prime then factoring is easy. I guess any such result is not known.<br /><br />Anon 3.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54645748272808711672009-08-04T15:46:26.204-05:002009-08-04T15:46:26.204-05:00Deterministic prime generation is not very useful ...Deterministic prime generation is not very useful for most crypto, but not for the reason you suggest.<br /><br />For DLOG type systems (e.g. ElGamal variants that are widely used), deterministic prime generation is fine. The issue is that a random prime is likely "better," in terms of producing a hard instance of the problem you're dealing with.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74680085611868350392009-08-04T14:20:54.503-05:002009-08-04T14:20:54.503-05:00(Actually, for crypto applications, we'd likel...(Actually, for crypto applications, we'd likely just keep using Miller-Rabin.)harrisonhttp://harrisonbrown.wordpress.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74775949529846655522009-08-04T14:19:44.725-05:002009-08-04T14:19:44.725-05:00Lance: For crypto applications, we'd just move...Lance: For crypto applications, we'd just move the randomness elsewhere; i.e., Alice would pick two primes at least 2^500 + x, where x is some "random" 490-bit number.harrisonhttp://harrisonbrown.wordpress.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19473373766325264822009-08-04T13:26:27.211-05:002009-08-04T13:26:27.211-05:00One correction:
The should be about "Log(n)&...One correction:<br /><br />The should be about "Log(n)" integers, not "N/Log(n)".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54925189639871758362009-08-04T13:23:44.105-05:002009-08-04T13:23:44.105-05:00I guess what I mean is an explicit function f_N su...I guess what I mean is an explicit function f_N such that for every integer x in [N, 2N] f_N(x) is a prime in [N, 2N], and for every prime p in [N, 2N] there are approximately N/log(N) integers such that f_N(x)=p. <br /><br />This is probably FAR too much to hope for!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83719443966947829742009-08-04T13:10:52.448-05:002009-08-04T13:10:52.448-05:00Anon 5, we already know how to do this, if I under...Anon 5, we already know how to do this, if I understand your comment correctly.<br /><br />Use random bits to pick a random number from the interval, and check if the number is prime or not and repeat until you find a prime. The primes are dense enough that you will find a prime quickly with high probability.<br /><br />If you really want to be stingy about the randomness, after you pick the first number uniformly at random, you can recycle the randomness using extractors so that you don't really need to add much more randomness to get a new uniform sample.<br /><br />Since the primes have relatively high density in intervals, you cannot get a much more efficient solution (in terms of randomness used), than the one above.Anup Raohttps://www.blogger.com/profile/14683815968695885450noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47436289599358815152009-08-04T12:53:23.762-05:002009-08-04T12:53:23.762-05:00Perhaps the ideal situation would be some sort of ...Perhaps the ideal situation would be some sort of (family of) deterministic maps which could take a random seed as input and output a prime which is approximately uniform on some interval.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57483416934837174312009-08-04T11:58:22.346-05:002009-08-04T11:58:22.346-05:00Anon 3: Suppose Alice use a deterministic prime fi...Anon 3: Suppose Alice use a deterministic prime finding algorithm to find two primes p and q at least 2^500 and multiply then together to get n=pq to use in say RSA. Eve could use the same algorithm, get the same p and q and decode messages at will.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15309884589344919272009-08-04T11:09:03.863-05:002009-08-04T11:09:03.863-05:00Oddly enough we would usually prefer a probabilist...<i>Oddly enough we would usually prefer a probabilistic over the deterministic method to find primes. Otherwise the adversary can use the same deterministic procedure and factor your number as easily as you put it together</i> <br /><br />Is that easy to see? Sorry if it is a stupid question.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74797159961121186652009-08-04T10:51:53.884-05:002009-08-04T10:51:53.884-05:00I have a basic question about this polymath stuff....I have a basic question about this polymath stuff. If someone not participating in the discussion comes up with a solution, would his or her credi be diminished by the suspicion that he/she somehow benefitted from the discussions, even though this might not be the case. I believe that someone not participating in such a project is under no obligation to quote or cite any unpublished but new fact unearthed during the discussions. But of course for some one participating in the project, not doing so would be dishonest. Does one need to register somewhere in order to view the postings ? Even if this is the case, I am afraid because of seepage in a large community, facts unearthed but unpublished would become known as "common knowledge" -- and this would be to the detriment of individual researchers thinking about the same questions. <br /><br />Have these questions been raised already in some forum ? The seem to be natural concerns.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67958573114504556442009-08-04T10:43:09.035-05:002009-08-04T10:43:09.035-05:00There's another motivation to deterministicall...There's another motivation to deterministically find large primes: such primes need to be generated to run deterministic algorithms that perform field operations over large fields.<br /><br />For example, there have been some extractor algorithms that involve treating the input as elements in a prime field and then doing some field operations with them. To make such an algorithm truly explicit, one needs to be able to generate a large enough prime deterministically.Anup Raohttps://www.blogger.com/profile/14683815968695885450noreply@blogger.com