mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2020-03-29, 19:19   #1
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

22×17×19 Posts
Default Prime numbers with P-1 properties ( or smooth primes)

Is it possible to write program that will produce primes that have P-1smooth properties ?
pepi37 is offline   Reply With Quote
Old 2020-03-29, 19:32   #2
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Out of my Body

31×59 Posts
Default

Quote:
Originally Posted by pepi37 View Post
Is it possible to write program that will produce primes that have P-1smooth properties ?

It is very easy to write programs that will produce integers that are N-1 smooth and then check to see if they are prime. Are you asking for algorithms to produce guaranteed primes?
Highly probable primes?
a1call is offline   Reply With Quote
Old 2020-03-29, 21:47   #3
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

22×17×19 Posts
Default

Quote:
Originally Posted by a1call View Post
It is very easy to write programs that will produce integers that are N-1 smooth and then check to see if they are prime. Are you asking for algorithms to produce guaranteed primes?
Highly probable primes?
It must be primes not PRP
Yes I ask something that I can run so algo produce and give me some primes with properties

Last fiddled with by pepi37 on 2020-03-29 at 21:49
pepi37 is offline   Reply With Quote
Old 2020-03-29, 23:19   #4
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Out of my Body

182910 Posts
Default

I wasn't referring to PRP's. A PRP that is P-1 smooth can easily be proven prime (if it is indeed prime). A multiple of (small) primes + 1 is more likely/probable to be prime if it is not much larger than the largest factor of P-1. On the other hand if it is much greater than it then the probability of it being prime decreases the larger it gets. If there was a generally known algo that would produce guaranteed large primes then this site world have closed shop long ago.

Last fiddled with by a1call on 2020-03-29 at 23:26
a1call is offline   Reply With Quote
Old 2020-03-29, 23:30   #5
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

24148 Posts
Default

Quote:
Originally Posted by a1call View Post
It is very easy to write programs that will produce integers that are N-1 smooth and then check to see if they are prime. Are you asking for algorithms to
Highly probable primes?

From your first answer it is very easy, now we are in the point ... that is not easy?
pepi37 is offline   Reply With Quote
Old 2020-03-30, 00:02   #6
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

107B16 Posts
Default

a1call is trying to point out (I think?) that it's much easier to construct smooth numbers and then test them for primality than it is to construct prime numbers and then test them for smoothness.

How many primality tests you'll need to find a smooth prime depends in large part on how big you want these things to be... but the "N+1" test will be a proof of primality, and doesn't take much longer than prp.
VBCurtis is offline   Reply With Quote
Old 2020-03-30, 00:40   #7
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

22·17·19 Posts
Default

So to clarify my idea. Prime 95 can do P-1. And those method can find fairly large factors. Of course it doesnot find all factors like "standard" sieve but find something that regular sieve will never find because we all do sieve well below .
So I would like ( that is idea and I dont know how to make it) to use P-1 primes for making sieve.


For example


641146783318960453 | 93*10^1039332-1
3060840294625372969 | 5*10^1037726-1
1778461772711066380507 | 6*10^1038514-1

If it is complicated to make this program I would like some kind of generator of "smooth" primes. It is easy to enter it in script and run PFGW: he will be check divisibility and if factor is found will get zero as result. :)
So that tool can remove some extra factors before we start processing.
Just is problem how to generate those primes with such properties

Last fiddled with by pepi37 on 2020-03-30 at 00:47 Reason: add more info
pepi37 is offline   Reply With Quote
Old 2020-03-30, 02:14   #8
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

4,219 Posts
Default

It seems like you want to do P-1 testing on a list of candidates that survived a sieve, but you've set up a rather convoluted way to try to set that up.

Could you maybe try again to explain what your "sieve" would do, or why it would be more effective than either regular P-1 testing or more regular sieving?
VBCurtis is offline   Reply With Quote
Old 2020-03-30, 10:25   #9
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

22×17×19 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
It seems like you want to do P-1 testing on a list of candidates that survived a sieve, but you've set up a rather convoluted way to try to set that up.

Could you maybe try again to explain what your "sieve" would do, or why it would be more effective than either regular P-1 testing or more regular sieving?

As I stated before
1. I know this is not "perfect sieve " and will not eliminate all but only limited number of candidates.
2. I dont know it is better or not from regular sieve process.
3. I start from position that regular sieve from standard user will never reach factors depth as can reach from P-1 method
4. I just reversed process : I try to take smooth primes and use them as platform for dividing candidates
5, Maybe it is totally insane idea, but unless I generate lets say 1000 -5000 those primes ( and try) I will never know is it or is it not.



So I ask once more, if someone here can write script or program that I can execute and will give me primes with those properties please help.


Maybe my English is not good to all of you and when I try to explain WHY I needed, and when I start to explain you ALWAYS think I am rude ,ungrateful and refuse to help me.


So if you can: help me, if not, forget about idea, I will try it to calculate at home how I know ( it will be hardest way , but in those days when we are all in quarantine there is time to spent)

Last fiddled with by pepi37 on 2020-03-30 at 11:08
pepi37 is offline   Reply With Quote
Old 2020-04-01, 10:49   #10
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

24148 Posts
Default

So there is no idea about this?
pepi37 is offline   Reply With Quote
Old 2020-04-02, 04:58   #11
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

2×5×859 Posts
Default

Quote:
Originally Posted by pepi37 View Post
So there is no idea about this?
The problem here is that sieving is done "by chunks". This means, you create a bitmap in your memory, where you put a bit to 1 for a number, and clear some bits to 0 when you find a factor of some number in your range. If you find a factor for some "bit" in your bitmap and clean it to zero, then other bits in the bitmap, residing at different, deterministic "offsets" compared with the first, can be cleared to zero, by modularity criterias. This is how every sieve works. Now, if your factor is small, then the "offset" is small, because the offset is either the factor itself, or some divisor of the eulerphy of the factor (well, this depends on the properties of the sequence you sieve, but let's ignore this for now). For example, if your factor is 3, then every second, or every third (depending on the sequence) bit in your bitmap can be cleared. By this you eliminate a lot of candidates (like half of them, or a third). Now, if your factor is getting larger, you eliminate less candidates from the bitmap, for one factor. For very large factors, you only eliminate one single candidate from the bitmap (and only if it was not already eliminated before).

Now, thinking about P-1, you must do P-1 effectively to find out a factor (or more) for each candidate, and once you found that factor, there are zero chances that you can use that factor to eliminate other candidates. For some sequences (like mersenne numbers with prime exponents) it is even proved that they do not share common factors.

Therefore, in this respect, your "sieving" doesn't do any better than what was already suggested (i.e. do P-1 for all remaining candidates, and eliminate as much as possible from them before going to LLR or PFGW), no matter what and how you find "smooth numbers", or how you "sieve".

Even assuming that your sequence allows multiple candidates to have the same factors, these factors that you find by P-1 are so large (of course, if sieving with small primes was properly done) that there are zero chances for one factor to eliminate more than one candidate, because your "chunk" you sieve is extremely small compared with the factor. You will need to store trillions of trillions of bits in the memory to have a "worthy" sieve with such large primes. The problem is the chunks you sieve are so small... even if you fill all your RAM with a sieve bitmap.

Last fiddled with by LaurV on 2020-04-02 at 05:04
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Why are numbers sum(2^(k*c)) smooth? preda Math 11 2018-08-30 17:35
Not smooth enough numbers Sam Kennedy Factoring 5 2012-11-10 07:54
Properties of Mersenne numbers kurtulmehtap Math 31 2011-01-10 00:15
Smooth and rough numbers CRGreathouse Math 3 2009-05-25 05:26
Smooth Numbers Yamato Math 1 2005-12-11 11:09

All times are UTC. The time now is 20:05.

Tue Jul 14 20:05:30 UTC 2020 up 111 days, 17:38, 0 users, load averages: 2.92, 2.56, 2.11

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.