Prime numbers with P-1 properties ( or smooth primes)
 

Is it possible to write program that will produce primes that have P-1smooth properties ?

[QUOTE=pepi37;541260]Is it possible to write program that will produce primes that have P-1smooth properties ?[/QUOTE]


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?

[QUOTE=a1call;541262]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?[/QUOTE]
It must be primes not PRP
Yes I ask something that I can run so algo produce and give me some primes with properties

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.:smile:

[QUOTE=a1call;541262]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?[/QUOTE]


From your first answer it is very easy, now we are in the point ... that is not easy?

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.

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

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?

[QUOTE=VBCurtis;541294]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?[/QUOTE]


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)

So there is no idea about this?

[QUOTE=pepi37;541468]So there is no idea about this?[/QUOTE]
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 [U]other[/U] 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.