Sieve needed for k*b1^m*b2^n+1

[cheesehead]

Originally Posted by geoff

23 is a prime not of the form k*3^3*5^2+1.

But it is of the form

k*b1^m*b2^n+1 where b1 and b2 are prime bases > 2, bases differing and k is even

k = 2

b1 = 11

m = 1

b2 = any odd prime but 11

n = 0

[beyastard]

I do understand EVERY prime with no exception can be represented as
k*b1^n1*b2^n2+1 if b1 = n1 = b2 = n2 = 1 and k = p-1/2. So an exercise
to find a prime NOT of this form is simply futile. If b1 and b2 are prime
bases > 2 and differing and n1 and n2 are > 0, k even, then there are
primes NOT of this form and the smallest you can represent would be
2*3^1*5^1+1 = 31, therefore, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 are NOT
of this form.

But from what I see, a sieve of this form can and will allow people to find
primes currently unknown. Also, I believe sieving across n1 or n2 will be a
more efficient use of time instead of sieving across k in a search for a
large prime. I think both b1 and b2 should be prime bases and k should be
chosen so it does not share a factor with the bases and is even. Having
prime bases allows for easy factoring of p-1 so a BLS can be done.

As I have stated before, the largest prime I've found of this form is
9926*7^11387*11^14771+1 (25010 digits) but I have, since then,
realized 9926 has a factor of 7 so the correct prime would be
1418*7^11388*11^14771+1. Finding this prime was no easy task as I
cannot sieve this form and so have to use an ABC2 file with pfgw and prp
each and every candidate.

Again, I will state my case and say I believe a sieve of this form will allow
many more large primes to be discovered. As for those that say I haven't
been doing my "homework," since Dr Silverman's post I have download
vaious PDF's including:

A Computational Introduction to Number Theory and Algebra
by Victor Shoup
The ABC's of Number Theory
by Prof Noam D Elkies
Elementary Number Theory, A Computational Approach
by William Stein
Elementary Number Theory in Nine Chapters
by James J Tattersall
and even
Fast Generation of Random, Strong RSA Primes by R D Silverman

[R.D. Silverman]

Originally Posted by geoff

I am not a mathematician either, so perhaps someone can explain to me why searching for primes of the form k*3^3*5^2+1 say, is pointless but searching for primes of the form k*2^333333+1 is not?

Alright! I give up!

EVERY prime can be put into the form k * p1^n p2^m + 1
where k is even and p1, p2 are primes.

The O.P. placed no restriction on n or m.!!!!!!!

Suppose now we restrict to n,m > 0. Now, almost all primes
have a representation. I say 'almost all' in the measure-theoretic sense.
The exceptions form a set of density 0. Which ones can't? I leave it
as an exercise. Hint: "Think about the Germain primes".

Suppose now we restrict to n,m > 1. The set that has a representation
is no longer 'almost all primes', but it is a set of positive density. That
density is easy to compute. (Hint: "what fraction of even integers are
squarefee; now apply to having two distinct square factors).

Furthermore, a "sieve" in the sense originally requested is computationally
impossible. We want p-1 = k * p1^n, p2^m. The RHS has 5 (FIVE!)
free variables. Over which one shall we sieve? 5-Dimensional sieves
are somewhat difficult from a computational point of view.....

Finally, note that for ANY pair (p1, p2), there are infinitely many primes
of the requested form. Their density is also positive. (Think about the
PNT for AP).

In short, there are so many primes of this form that looking for them is
EASY. There is no 'research' here. The density of these primes is
well understood.

[R.D. Silverman]

Originally Posted by geoff

23 is a prime not of the form k*3^3*5^2+1. Why shouldn't someone search for those primes which are of this form? The sieve that was requested would allow them to do that efficiently.

23 - 1 = 2 * 11^1 * p^0 where p is any prime. 23 has the
requested form.

See my followup.

[R.D. Silverman]

Originally Posted by beyastard

If you read my first post you will see it's nothing more than a request for
a sieve of a specific form as there are none that I can find. I see nothing
in my request that can even be closely considered showing arrogance.

Also, one does not have to have "qualifications" to use a piece of software
to sieve, test for prp then verify prp's as prime. One only needs to know how
to use the software.

YOU claimed to be doing 'new research'. Blindly using software written
by others to implement algorithms that you do not understand is not
'research'. Blindly computing primes is not 'research'. Nor is it doing
mathematics.


And you did NOT request a 'sieve of a specific form'. You
said nothing at all about the 'form' of the sieve you wanted.

Damn it!! There are 5 variables involved! Over which variable(s) did
you want to sieve? Fix any 4 of them and the problem becomes a
simple sieve; trivial to implement.

A good learning exercize would be for you to write such a sieve yourself
instead of asking that it be handed to you. Learn the difficulties involved.
Learn the elementary number theory involved. Learn why such a general
sieve (in the sense you ask for) is computationally impossible.

OTOH, if you are just doing this for fun, that I can understand. But
it is not new, it is not research, and doesn't even add enough knowledge
to mathematics to make a decent undergraduate paper.

[TimSorbet]

Originally Posted by beyastard

Finding this prime was no easy task as I
cannot sieve this form and so have to use an ABC2 file with pfgw and prp
each and every candidate.

Run -f file.txt and PFGW will attempt to trial factor every number (to an automated depth) before PRPing it. Read pfgwdoc.txt to learn about the other options and how to tweak how much TF it tries.

[cheesehead]

Originally Posted by beyastard

I do understand EVERY prime with no exception can be represented as
k*b1^n1*b2^n2+1 if b1 = n1 = b2 = n2 = 1 and k = p-1/2. So an exercise to find a prime NOT of this form is simply futile.

That's why Silverman was saying that your search, as defined in the OP, was pointless. You'd simply be searching for any prime whatsoever.

That's the lesson to be learned from trying to find a prime that is NOT of the form defined in the OP. If you'd simply done that right away as requested, we'd have saved a lot of time.

If b1 and b2 are prime bases > 2 and differing and n1 and n2 are > 0, k even, then

... you have added a restriction (n1 and n2 are > 0) that was missing from the OP (where m and n were used in place of n1 and n2).

There's a difference between requiring (m, n > 0) and not requiring that.

But from what I see, a sieve of this form can and will allow people to find primes currently unknown.

Perhaps so ... because now you're talking about a different, more-restrictive form than you were originally talking about -- at least in the eyes of your readers.

Maybe you intended that the restriction (m, n > 0) be in place all along. Your examples in the OP all met that requirement. But you hadn't actually stated that restriction, and that's why your original proposal met with the reception that it did. We can't read your mind -- just the actual text.

As for those that say I haven't been doing my "homework," since Dr Silverman's post I have download vaious PDF's including:

< snip >

But your homework assignment wasn't to download PDFs; it was to try to find a prime that was not of the form you stated in your OP.

This was the first post where you've shown us that you made any attempt to do the actual "homework assignment" by Dr. Silverman. You hadn't shown us that in any post before #24.

[R.D. Silverman]

Originally Posted by cheesehead

That's why Silverman was saying that your search, as defined in the OP, was pointless. You'd simply be searching for any prime whatsoever.

The next assignment is to show that the restriction m,n > 0, is also
not very restrictive. I gave a hint.

I am still curious as to why the OP thinks that finding new primes
by blindly using someone else's software is 'research'.

[beyastard]

As you stated, "5-Dimensional sieves are somewhat difficult from
a computational point of view..." it can be reduced to 3 values.

Let FicSieve be the name of the fictional fixed-k sieve.

Command line can be something like:

>FictSieve --k=6 --b1=7 --n1=150000 --b2=11 --n2=2-150000 --pmin=2 --pmax=10000000 [etc]

The program checks to see if k shares any factors with b1 or b2,
if it does, it terminates with error message such as
"k shares base with b1/b2". If it shares no factors then it uses
k*b1^n1 as k1 so that it becomes k1*b2^n2+1 and sieves across
the n2 variable, all others being fixed. Basically, a k*b^n+1
sieve with a k value > 100k digits and having a large number
of small factors (above example being 2*3*7^150000).

An alternative (and probably better method) would be where you
can input a term for k on the commandline so only 3 terms will
be needed, for example:

>FictSieve --k=2*3*7^150000 --b=11 --n=2-150000 --pmin=2 --pmax=10000000 [etc]

As I am not familiar with sieves and have no well-commented source
of a few different kinds to study and learn about, I am not sure
if such a task is feasible. If it is, I would probably say that
because the above combining of terms into k1 creates such a large
value, a library such as GMP may be required. Also, if I am able to
learn the "mechanics" of sieves, I'd tackle this problem myself.

And yes, Doc, I do see flaws in this form but still trying to work
through them as I see there is potential in forms of this kind, i.e.,
k*b1^n1*b2^n2...bi^ni+1, as p-1 is easily factored into small primes
(since practically all the factors are known beforehand). An easily
factored number really helps in a BLS test for primality. The biggest
hurdle is reducing all the k*b(i-1)^n(i-1) into a single value to
sieve for k1*bi^ni+1 as k1 will be such a large number.

As you have stated, "In short, there are so many primes of this form
that looking for them is EASY." So, in a nutshell, sieving for primes
of this form will help increase the number of large primes discovered.
The biggest hurdle to overcome will be finding an efficient method of
doing so.

[R.D. Silverman]

Originally Posted by beyastard

So, in a nutshell, sieving for primes
of this form will help increase the number of large primes discovered.

.

So? Other than being a stamp collection, please explain the value
of increasing the number of known large primes. What will you do with these
primes? What mathematics will be learned? What problems will they help
solve? What algorithms will be improved by searching for them?

[R.D. Silverman]

Originally Posted by beyastard

As I am not familiar with sieves and have no well-commented source
of a few different kinds to study and learn about,

Under the assumption that you already know how to write code,
studying existing code is the WORST way to learn about sieves.

Start by learning the basic number theory behind them.

Then implement one yourself. And one does NOT need an MP
library to sieve numbers of the form you suggest as long as k,
and the two primes are themselves only single precision.
And even if they are multi precision, all one needs to sieve through
primes less than 2^31 (on a 32-bit machine) is a simple routine
that returns the remainder when an MP number is divided by a single
precision number. Get a copy of Knuth Vol II. Read the section on
multi-precision arithmetic. He also discusses how to perform a sieve.