mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2016-03-13, 06:26   #1
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

197 Posts
Post 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.
PawnProver44 is offline   Reply With Quote
Old 2016-03-13, 07:06   #2
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

100111100010012 Posts
Default

Please explain what you mean by "I factored this number to 33.33%"
Uncwilly is online now   Reply With Quote
Old 2016-03-13, 07:19   #3
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

It means that log(known factors)/log(number) > 1/3
Dubslow is offline   Reply With Quote
Old 2016-03-13, 09:49   #4
NBtarheel_33
 
NBtarheel_33's Avatar
 
"Nathan"
Jul 2008
Maryland, USA

21338 Posts
Default

Quote:
Originally Posted by PawnProver44 View Post
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 View Post
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 View Post
I can run Pfgw so I can use arithmetic progressions (k) to find this prime.
What prime?

Quote:
Originally Posted by PawnProver44 View Post
The only problem is when I submit this prime,
What prime?

Quote:
Originally Posted by PawnProver44 View Post
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 View Post
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.

Last fiddled with by NBtarheel_33 on 2016-03-13 at 10:04
NBtarheel_33 is offline   Reply With Quote
Old 2016-03-13, 10:24   #5
axn
 
axn's Avatar
 
Jun 2003

22×3×433 Posts
Default

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.
axn is offline   Reply With Quote
Old 2016-03-13, 12:34   #6
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

427010 Posts
Default

Quote:
Originally Posted by NBtarheel_33 View Post
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.

Last fiddled with by Mini-Geek on 2016-03-13 at 12:35
Mini-Geek is offline   Reply With Quote
Old 2016-03-13, 18:46   #7
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

197 Posts
Post

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.

Last fiddled with by wblipp on 2016-03-16 at 17:46 Reason: fix quote box
PawnProver44 is offline   Reply With Quote
Old 2016-03-13, 19:52   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5·787 Posts
Default

Quote:
Originally Posted by PawnProver44 View Post

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

Last fiddled with by paulunderwood on 2016-03-13 at 19:55
paulunderwood is offline   Reply With Quote
Old 2016-03-13, 21:21   #9
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

32×101 Posts
Default

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.

Last fiddled with by danaj on 2016-03-13 at 21:27 Reason: links to Maurer/S-T
danaj is offline   Reply With Quote
Old 2016-03-13, 22:24   #10
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·1,087 Posts
Default

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 is offline   Reply With Quote
Old 2016-03-13, 22:30   #11
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2×1,087 Posts
Default

Quote:
Originally Posted by PawnProver44 View Post
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.
a1call is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 15:17.


Sun Dec 5 15:17:47 UTC 2021 up 135 days, 9:46, 1 user, load averages: 1.69, 1.40, 1.33

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.