Prime Pages How to's

PawnProver44 · 2016-03-13, 06:26

I have seen most primes on the Top 5000 are of the form k*2^n+1, however I want to find an "ordinary" prime. I came up with the idea of picking already large known primes and multiplying them together with another random number. I can run Pfgw so I can use arithmetic progressions (k) to find this prime. The only problem is when I submit this prime, how do I let the editors and others know I factored this number to 33.33%. Is there anwhere I should list the known factors in order to prove the number prime. Please let me know. Thanks.

Uncwilly · 2016-03-13, 07:06

Please explain what you mean by "I factored this number to 33.33%"

Dubslow · 2016-03-13, 07:19

It means that log(known factors)/log(number) > 1/3

NBtarheel_33 · 2016-03-13, 09:49

Quote:

Originally Posted by PawnProver44

I have seen most primes on the Top 5000 are of the form k*2^n+1, however I want to find an "ordinary" prime.

There is a reason for this. Primes of certain special forms (e.g. Mersenne primes) will often admit computationally feasible, deterministic algorithms (e.g. the Lucas-Lehmer test) that allow us to examine candidates well into the millions of digits in length. On the other hand, if you were to simply type out a random odd integer having many more than 200-300 digits, you will quickly be at the limit of even the newest, most specialized tools available for proving primality. This coming Friday, March 18th, is the 25th anniversary of the RSA Challenge, which originally asked for the factorizations of several large integers ranging in size from one hundred to five hundred decimal digits. Originally, many of these factorizations had five- and six-figure (in US$) prizes attached to them, though these prizes have since been retracted. Note just how many of these numbers - starting at a mere 220 digits - remain unfactored even after a quarter-century of effort. Factoring (and by extension, primality proving) of integers not of a special form becomes extremely difficult, extremely quickly.

Quote:

Originally Posted by PawnProver44

I came up with the idea of picking already large known primes and multiplying them together with another random number.

You realize that a prime number multiplied by any number other than 0 or 1 is by definition no longer prime, right? The product of your multiplication has at least two proper factors: the large prime and the other "random number". It is therefore composite.

Quote:

Originally Posted by PawnProver44

I can run Pfgw so I can use arithmetic progressions (k) to find this prime.

What prime?

Quote:

Originally Posted by PawnProver44

The only problem is when I submit this prime,

What prime?

Quote:

Originally Posted by PawnProver44

how do I let the editors and others know I factored this number to 33.33%.

Whatever "factored to 33.33%" means (let us suppose that it means that you trial-divided your candidate by every prime between 2 and one-third of the square root of the candidate - further supposing that this is even computationally feasible), you likely have not proven primality. To prove primality by factoring $n$ , you need to trial divide by every single prime between 2 and $\sqrt{n}$ , and thus show that no proper factors exist.

Quote:

Originally Posted by PawnProver44

Is there anwhere I should list the known factors in order to prove the number prime. Please let me know. Thanks.

My suggestion is to read this forum, the Prime Pages, some of the number theory articles on Wikipedia, etc. to get a basic understanding of elementary definitions, terminology, and notation. You seem to be confused on the definitions of "prime" and "factor", for example. If you have proven a number prime, you would not have factors to list, because no factors exist...by definition of "prime". If you are listing factors, then you are demonstrating that a number is composite - the exact opposite of prime. Here is a concrete example:

74,207,281 is a prime number because there are no integers other than 1 and 74,207,281 that evenly divide 74,207,281.
On the other hand, 17,350,618 is not a prime number because there are integers other than 1 and 17,350,618 that evenly divide 17,350,618, to wit:
- 2 divides 17,350,618 because 17,350,618 = 2 * 8,675,309.
- 8,675,309 divides 17,350,618 because 17,350,618 = 8,675,309 * 2.
- Therefore, we can exhibit the integers 2 and 8,675,309 as factors of 17,350,618, and furthermore as proof that 17,350,618 is composite, i.e. not prime.

Please feel free to ask questions and start discussions as you work your way through some of the elementary material. Understanding the foundations (i.e. the "rules of the game") - notation, terminology, basic theorems, etc. - will give you a much greater enjoyment of the subject and will also allow you to more easily communicate and collaborate with the Mersenne Forum and GIMPS communities.

axn · 2016-03-13, 10:24

I don't know what actually OP means. But the basic idea is that you'll take a bunch of known primes and compute N=k*P1*P2..Pn+/-1. By construction, we know the factorization of N-1 (or N+1). If N is a PRP, we should be able to prove it relatively easily.

I don't where arithmetic progressions fit in this scheme.

Mini-Geek · 2016-03-13, 12:34

Quote:

Originally Posted by NBtarheel_33

There is a reason for this. Primes of certain special forms (e.g. Mersenne primes) will often admit computationally feasible, deterministic algorithms (e.g. the Lucas-Lehmer test) that allow us to examine candidates well into the millions of digits in length. On the other hand, if you were to simply type out a random odd integer having many more than 200-300 digits, you will quickly be at the limit of even the newest, most specialized tools available for proving primality. This coming Friday, March 18th, is the 25th anniversary of the RSA Challenge, which originally asked for the factorizations of several large integers ranging in size from one hundred to five hundred decimal digits. Originally, many of these factorizations had five- and six-figure (in US$) prizes attached to them, though these prizes have since been retracted. Note just how many of these numbers - starting at a mere 220 digits - remain unfactored even after a quarter-century of effort. Factoring (and by extension, primality proving) of integers not of a special form becomes extremely difficult, extremely quickly.

You seem to be thinking that the best way to find general-form primes is as difficult as factoring them. This is not the case. PRP tests (probable) can be done on numbers with millions of digits, and ECPP (a proof) can be done on numbers with tens of thousands of digits.

Still, OP seems to be basing his work on factorization, so what you wrote can (partially) apply.

PawnProver44 · 2016-03-13, 18:46

Quote:

You realize that a prime number multiplied by any number other than 0 or 1 is by definition no longer prime, right? The product of your multiplication has at least two proper factors: the large prime and the other "random number". It is therefore composite.

Multiply a few large known prime from either primes.utm.edu or factordb.com with another large random number, so then add 1 to that product p. p+1 may not be prime however, there would exist a prime of the form k*p+1, with our product p. However most people do not think of "creating" factors randomly. To explain what I mean, I formed this prime by picking 6 random primes around 500 digits, multiplying them with a random number, then adding 1. http://factordb.com/index.php?id=1100000000827275595. You will see that this prime is using the N-1 method. See, I originally wanted to find an ordinary, random prime like this around 500k digits.

paulunderwood · 2016-03-13, 19:52

Quote:

Originally Posted by PawnProver44

Multiply a few large known prime from either primes.utm.edu or factordb.com with another large random number, so then add 1 to that product p. p+1 may not be prime however, there would exist a prime of the form k*p+1, with our product p. However most people do not think of "creating" factors randomly. To explain what I mean, I formed this prime by picking 6 random primes around 500 digits, multiplying them with a random number, then adding 1. http://factordb.com/index.php?id=1100000000827275595. You will see that this prime is using the N-1 method. See, I originally wanted to find an ordinary, random prime like this around 500k digits.

There is nothing to stop you doing this. It will take much longer to do each individual test of numbers where on average the primes are more spread apart, plus you will be using generic modular arithmetic of the underlying library which slows things down further. However, you might get lucky by striking gold on your first attempt

danaj · 2016-03-13, 21:21

As far as I can tell, the OP is suggesting doing one step of Maurer's or Shawe-Taylor's method for generating random proven primes. Which is just applying Pocklington, Generalized Pocklington, BLS75 theorem 5, etc. Rather than struggle with the ambiguity of what is getting factored in his text, I'll just state this method.

For instance, using the simple BLS75 theorem 3,

1. Let P be some odd prime with a proof already available.

2. Let M be an arbitrary even number 1 < M < 4P.

3. Let N = P*M+1. Hence N-1 = P*M. Verify 2P+1 > sqrt(N). This should be true from our selection in step 2, but we should always include a verification of necessary conditions to protect from programmers or post-writers getting something off by 1.

4. Run some sort of compositeness test on N (e.g. a little trial division plus a Fermat test). If composite, go to 2.

5. Find an a such that $a^{(N-1)/2} \equiv -1 \pmod N$ and $a^{M/2} \not\equiv -1 \pmod N$ . Search prime 'a' from 2 to 100 for instance. If we cannot find one, then go to 2.

6. By BLS75 theorem 3, N is prime (assuming P is prime).

There are some decision points that are tunable. If the test in step 4 is stringent, e.g. BPSW, then the chance step 5 will fail approaches zero, so we should increase the number of 'a' values we examine. Alternately we could make the step 4 test cheap (e.g. divisibility or a single Fermat test) then assume some composites will go to step 5, so we shorten its search.

We could improve this with BLS theorem 5 to allow M and hence N to be much larger (which is where the 33.33% comes in, though there are linear factors as well). The basic structure is pretty similar (choose an M, get an N value, do compositeness test, find 'a' values for proof).

The same thing can be done with ECPP proofs, though more involved. In either case, we're reversing the steps to remove the difficult factoring part. But we end up with a proof of some semi-arbitrary number, which is good enough for these sorts of records and useful for selecting random primes, but of course of completely different utility than a "is N prime" question.

There are some non-trivial operations involved in this, and once N is large enough (e.g. 10k digits) step 4 starts taking appreciable time so we'd want to add some fast pre-tests or even sieving. I have no idea where arithmetic progressions come in.

a1call · 2016-03-13, 22:24

Quote:

I formed this prime by picking 6 random primes around 500 digits, multiplying them with a random number, then adding 1. http://factordb.com/index.php?id=1100000000827275595.

Why not register and login before submitting primes?
That way it will be registered under your name rather than others and kept track of here:
http://factordb.com/certtop.php

a1call · 2016-03-13, 22:30

Quote:

Originally Posted by PawnProver44

I have seen most primes on the Top 5000 are of the form k*2^n+1, however I want to find an "ordinary" prime. I came up with the idea of picking already large known primes and multiplying them together with another random number. I can run Pfgw so I can use arithmetic progressions (k) to find this prime. The only problem is when I submit this prime, how do I let the editors and others know I factored this number to 33.33%. Is there anwhere I should list the known factors in order to prove the number prime. Please let me know. Thanks.

The utm.edu domain has been inaccessible all day, but when up there is a contact the editors form that you can use to contact them.

2016-03-13, 06:26	#1
PawnProver44 "NOT A TROLL" Mar 2016 California 197 Posts	Prime Pages How to's I have seen most primes on the Top 5000 are of the form k*2^n+1, however I want to find an "ordinary" prime. I came up with the idea of picking already large known primes and multiplying them together with another random number. I can run Pfgw so I can use arithmetic progressions (k) to find this prime. The only problem is when I submit this prime, how do I let the editors and others know I factored this number to 33.33%. Is there anwhere I should list the known factors in order to prove the number prime. Please let me know. Thanks.

2016-03-13, 21:21	#9
danaj "Dana Jacobsen" Feb 2011 Bangkok, TH 2²·227 Posts	As far as I can tell, the OP is suggesting doing one step of Maurer's or Shawe-Taylor's method for generating random proven primes. Which is just applying Pocklington, Generalized Pocklington, BLS75 theorem 5, etc. Rather than struggle with the ambiguity of what is getting factored in his text, I'll just state this method. For instance, using the simple BLS75 theorem 3, 1. Let P be some odd prime with a proof already available. 2. Let M be an arbitrary even number 1 < M < 4P. 3. Let N = PM+1. Hence N-1 = PM. Verify 2P+1 > sqrt(N). This should be true from our selection in step 2, but we should always include a verification of necessary conditions to protect from programmers or post-writers getting something off by 1. 4. Run some sort of compositeness test on N (e.g. a little trial division plus a Fermat test). If composite, go to 2. 5. Find an a such that $a^{(N-1)/2} \equiv -1 \pmod N$ and $a^{M/2} \not\equiv -1 \pmod N$ . Search prime 'a' from 2 to 100 for instance. If we cannot find one, then go to 2. 6. By BLS75 theorem 3, N is prime (assuming P is prime). There are some decision points that are tunable. If the test in step 4 is stringent, e.g. BPSW, then the chance step 5 will fail approaches zero, so we should increase the number of 'a' values we examine. Alternately we could make the step 4 test cheap (e.g. divisibility or a single Fermat test) then assume some composites will go to step 5, so we shorten its search. We could improve this with BLS theorem 5 to allow M and hence N to be much larger (which is where the 33.33% comes in, though there are linear factors as well). The basic structure is pretty similar (choose an M, get an N value, do compositeness test, find 'a' values for proof). The same thing can be done with ECPP proofs, though more involved. In either case, we're reversing the steps to remove the difficult factoring part. But we end up with a proof of some semi-arbitrary number, which is good enough for these sorts of records and useful for selecting random primes, but of course of completely different utility than a "is N prime" question. There are some non-trivial operations involved in this, and once N is large enough (e.g. 10k digits) step 4 starts taking appreciable time so we'd want to add some fast pre-tests or even sieving. I have no idea where arithmetic progressions come in. Last fiddled with by danaj on 2016-03-13 at 21:27 Reason: links to Maurer/S-T

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Prime Pages Achievable Forms?	PawnProver44	Miscellaneous Math	1	2016-04-08 11:27
Prime pages question	jasong	jasong	7	2013-03-09 12:10
TPS prime pages password	Oddball	Twin Prime Search	5	2011-03-20 04:50
What's up with the Prime Pages?	Unregistered	Information & Answers	1	2007-06-09 02:44
How do I determine the xth-highest prime on prime pages?	jasong	Data	7	2005-09-13 20:41

2016-03-13, 07:06	#2
Uncwilly 6809 > 6502 """"""""""""""""""" Aug 2003 101×103 Posts 9784₁₀ Posts	Please explain what you mean by "I factored this number to 33.33%"

2016-03-13, 07:19	#3
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 3×29×83 Posts	It means that log(known factors)/log(number) > 1/3

2016-03-13, 10:24	#5
axn Jun 2003 5,051 Posts	I don't know what actually OP means. But the basic idea is that you'll take a bunch of known primes and compute N=kP1P2..Pn+/-1. By construction, we know the factorization of N-1 (or N+1). If N is a PRP, we should be able to prove it relatively easily. I don't where arithmetic progressions fit in this scheme.