mpz_probab_prime_p

[Jason Moxham]

Hi

I've obsoleted then MPIR function

int mpz_probab_prime_p (mpz_t N, int REPS)

The reasons for this are mainly that the random state used in the above
algorithm is reset on every function call. So two consecutive calls to this
function are NOT independent. The other reason is that the parameter REPS is
dependant on the algorithm used(which is Miller-Rabin).

We will maintain the old function interface for some time to come to maintain
compatibility.

The question remains as what to offer as a replacement. We could of course
offer no replacement? or at the bare minimum

int mpz_probable_prime_p (mpz_t N, int REPS, gmp_randstate_t STATE)

However I would like to suggest something like this.

Note: Some of these may not be functions but macros.

int mpz_practical_probable_prime_p(mpz_t N, gmp_randstate_t STATE)
return true if N is probably a prime and return false if N is certainly a
composite or (0,1,-1) . NOTE: I say N is probably a prime , NOT N is a
probable prime , which can mean something specific.
This would be the function that you would use in a integer prime factorization
program , optimized for speed , implemented as a bit of trial division , and
one iteration of small base random strong pseudoprime test , with corners cut
to make run faster(on average).

And the mathematically better defined
int mpz_probable_prime_p(mpz_t N, int PROB, gmp_randstate_t STATE)
return true iff N is a probable prime with less than 1/2^PROB error. This
allows us to use different algorithms to achieve the same maximum probability
of error. This would implemented robustly using the random strong pseudoprime
test , RQFT test and others. The underlying functions for this could be
exposed to the user, and shared with some other new mpz functions.

Jason

[Jason Moxham]

On Monday 17 August 2009 14:02:13 Jason Moxham wrote:
> Hi
>
> I've obsoleted then MPIR function
>
> int mpz_probab_prime_p (mpz_t N, int REPS)
>
> The reasons for this are mainly that the random state used in the above
> algorithm is reset on every function call. So two consecutive calls to this
> function are NOT independent. The other reason is that the parameter REPS
> is dependant on the algorithm used(which is Miller-Rabin).
>
> We will maintain the old function interface for some time to come to
> maintain compatibility.
>
> The question remains as what to offer as a replacement. We could of course
> offer no replacement? or at the bare minimum
>
> int mpz_probable_prime_p (mpz_t N, int REPS, gmp_randstate_t STATE)
>
> However I would like to suggest something like this.
>
> Note: Some of these may not be functions but macros.

Here are the new functions:

int mpz_practical_prime_p(mpz_t N, gmp_randstate_t STATE,unsigned long div)

return true if N is probably a prime and return false if N is certainly a
composite or (0,1,-1) . NOTE: I say N is probably a prime , NOT N is a
probable prime , which can mean something specific.
This would be the function that you would use in a integer prime
factorization program , optimized for speed , implemented as a bit of trial
division , and one iteration of small base random strong pseudoprime test ,

with corners cut to make run faster(on average).div is a trial division bound
of which you have allready searched up to.

And the mathematically better defined

int mpz_probable_prime_p(mpz_t N, int PROB, gmp_randstate_t STATE,unsigned
long div)

return true iff N is a probable prime with less than 1/2^PROB error. This
allows us to use different algorithms to achieve the same maximum
probability of error. This would implemented robustly using the random

strong pseudoprime test , RQFT test and others. div is a trial division bound
of which you have allready searched up to.

I have said that the new function interfaces are preliminary , in case we want
to change anything.

This brings into question what the new mpz_next_probable_prime should do , ie
should it be practical or probable (with a defined probability) , at the
moment it is just the old mpz_probab_prime with 5 reps which would be
equivalent to a probability of 1 in 4^5 . Note: this is a maximum error and
is WAY over the top of most reasonable applications.

What do people think? What should we do ? , I am leaning towards having both
next_practical and next_probable(with a stated probability)

Jason

Note: The trial division I have used in the above fn's is just for
correctness , I will put faster code in a few days , so dont laugh at to
much :)

[Jason Moxham]

Or getting rid of the mpz_next_prime_thing all-together , cant say I like it
much. What do people use it for ?

The old function was mpz_nextprime_p . We obsoleted this function because it
was badly named (it was not necessarily prime) and even if we admit that ,
the random state used to generate the probable primes was not random , but
reset on each call.

[Bill Hart]

I don't personally like the name mpz_practical_prime_p(). The reason is that it doesn't mean anything particular to anyone but us.

Here's some random ideas. We could change the prototypes to:

mpz_is_probab_prime_p(mpz_t p, prime_alg_t alg, unsigned long iterations)

mpz_is_prime_p(mpz_t p)

where p is the number being checked for primality, alg specifies a algorithm (the prime_alg_t would be an enum enumerating possible algorithms) and the iterations thing is self explanatory.

The mpz_is_prime wouldn't need an algorithm specified as it should just do whatever is fastest to certify the prime.

mpz_next_probab_prime(mpz_t p, mpz_t old_p, prime_alg_t alg, unsigned long iterations)

mpz_next_prime(mpz_t p)

Again the flags and rationale would be the same.

The only thing which doesn't fit very well is the trial factoring thing. If the number has already been trial factored up to some bound then how would you specify that. But not all algorithms care about that.

Perhaps all the extra data about algorithm, iterations, trial factoring limit should be passed in in a single struct, a gmp_prime_t struct or something like that, which could be null if you really don't care and just want something quick and dirty with no special properties (like we currently have). So you'd have:

mpz_is_probab_prime_p(mpz_t p, mpz_prime_t inf)

mpz_is_prime_p(mpz_t p, mpz_prime_t inf)

mpz_next_probab_prime(mpz_t p, mpz_prime_t inf)

mpz_next_prime(mpz_t p, mpz_prime_t inf)

I don't know, this whole primality testing thing just opens a huge can of worms. I mean, the most efficient way of finding the nextprime is to first sieve which means you want to be setting up a persistent sieve. But that is not something you want to do with a type like that as every time the function is called you have to check if p is actually the last prime that was found in the associated sieve. Instead you want specific functions which initialise a sieve and find the next prime in the sieve given an offset in the sieve:

mpz_prime_sieve_init(mpz_sieve_t sieve, mpz_t start) - where start specifies the first number in the sieve (must be even and not 2)

mpz_next_prime(mpz_t p, mpz_t old_p, mpz_sieve_t sieve) - where old_p must specify a number which lies in the sieve, p will be the next prime after it

Of course to do *that* efficiently you need the an atkins sieve or the other algorithm whose name I forgot - the one miller used in his primepi implementation.

Bill.

2009/9/4 Jason Moxham <ja...@njkfrudils.plus.com>

[Cactus]

On Sep 4, 4:58 am, Bill Hart <goodwillh...@googlemail.com> wrote:

> I don't personally like the name mpz_practical_prime_p(). The reason is that
> it doesn't mean anything particular to anyone but us.

I also doubt that it will help to have two differenet functions that
appear to do the same job to anyone who is unaware of the subtleties
involved.

I would personally prefer to call this a test:

mpz_prime_test(mpz_t n, enum alg, uint trials) + rand_state?

to avoid potentially confusing names.

I am also uneasy about returning true for something that might be
false even if we do represent this uncertainty in the name.

How about this:

mpz_is_composite(mpz_t n) that returns 1 if composite or 0 if the
test fails (compositeness undetermined).

for Jason's 'practical prime' proposal?

We can then explain that this removes most composites rapidly and
allows the more costly but more precise prime tests for numers that
remain.

Brian

[Jeff Gilchrist]

On Thu, Sep 3, 2009 at 10:51 PM, Jason Moxham<ja...@njkfrudils.plus.com> wrote:

> Or getting rid of the mpz_next_prime_thing all-together , cant say I like it
> much. What do people use it for ?

I actually use it and find it very useful. If I'm doing some kind of
testing or other calculations on increasing primes it is very useful
just to call that function to get the next one to work with.

Right now unless you dig into the code it is hard to tell what the two
current prime functions really do. So a new defined function that
either provides a way to specify the algorithm to use or have
something very clearly defined would be a great benefit. If someone
is trying to do work that needs to be repeatable it would be good to
have a way for people to say, "Use MPIR with this is_prime/prob_prime
function using these parameters"

Jeff.

[Cactus]

On Sep 4, 11:03 am, Jeff Gilchrist <jeff.gilchr...@gmail.com> wrote:
> On Thu, Sep 3, 2009 at 10:51 PM, Jason Moxham<ja...@njkfrudils.plus.com> wrote:
> > Or getting rid of the mpz_next_prime_thing all-together , cant say I like it
> > much. What do people use it for ?
>
> I actually use it and find it very useful.  If I'm doing some kind of
> testing or other calculations on increasing primes it is very useful
> just to call that function to get the next one to work with.

Its normal use is to offer a fast way of first generating a random
number and then quickly finding the first likely prime above this
number without applying a relatively costly test to each number in
turn. This is normally done with a sieve for several hundred small
primes.

But as currently implemented it uses mpz_next_probable_prime()
directly and this is pretty useless since it applies a prime test to
numbers in turn. It doesn't even screen out even numbers!

Looking quickly at the code, it seems that a version with sieving has
been written but it hasn't been tested or enabled.

But I agree with Jeff - it is useful to be able to generate a random
number and then have a fast way of looking for possible primes above
this value to pass to a prime testing algorithm.

[Robert Gerbicz]

2009/9/4 Cactus <riem...@googlemail.com>

Looking quickly at the code, it seems that  a version with sieving has
been written but it hasn't been tested or enabled.

In fact for large n values it would be faster to use more primes at sieve using a remainder tree instead of one expensive division for each prime, what is the current code doing. This is a known trick, and discussed also on the gmp list as I can remember.

[Jason Moxham]

On Friday 04 September 2009 04:58:53 Bill Hart wrote:
> I don't personally like the name mpz_practical_prime_p(). The reason is
> that it doesn't mean anything particular to anyone but us.

I think this is an advantage. I dont want people to confuse this function with
any particular probable prime test , and get upset when they find out it is
no particular one ,and they wont find it in the mathematical literature
(why ? , because we have not shown any particular mathematical property is
true, eg like true for all n<10^15 , or true with an error rate of <1 in 2^10
etc). It's purpose is for factoring , where we want speed and reasonable
accuracy , and this function is ment to be it. As it is common in factoring
to do trial division , it is pointless to do it again , so that is why I
added the bound.I did think of adding a structure to pass other information ,
but that is overkill for the purpose of this function(if we do a real prime
test , then we should pass this sort of info).

I don't want to get into real prime tests yet , that is a whole new can of
worms.

We have obsoleted mpz_probab_prime_p because of reasons stated before, so we
have to replace the functionality of it with some new functions.
mpz_probab_prime_p was used in factoring and the new mpz_practical_prime_p is
my attempt at replacing it for that purpose.

The other use of mpz_probab_prime_p was to perform strong psuedoprime tests so
the user could say this number passed 10 reps of sprp tests. The new
mpz_probable_prime_p is my attempt at replacing this part , here we have
dropped any specification of a particular probable prime algorithm , this
gives us freedom to use faster variants , and the user still gets what they
wanted , a declaration of probable primeality with a given maximum error
rate.I put a trial div bound in here , as again it is a common thing to of
allready have done.

The other use of the old mpz_probab_prime_p was when the user specifically
wants a strong psuedoprime test performed and not something similar. I
haven't provided for this. We could certainly add specific functions for
this , for the moment the user can just call our new mpz_probable_prime_p
because that is the only test it uses at the moment.

Users should not care about the algorithms used , the functions should be
black boxes.

My main motivation was to replace the clearly poor functions we had with
something better. The new functions do solve the poor random state of the old
functions , and in principle , if you replace the old mpz_probab_prime_p in
your programs with the appropriate new function you should see a speed up. I
haven't actually written the new code yet for that.I do plan to add some of
these "missing" functions later , but I see how well this first lot go down

[Jason Moxham]

On Friday 04 September 2009 08:33:01 Cactus wrote:
> On Sep 4, 4:58 am, Bill Hart <goodwillh...@googlemail.com> wrote:
> > I don't personally like the name mpz_practical_prime_p(). The reason is
> > that it doesn't mean anything particular to anyone but us.
>
> I also doubt that it will help to have two differenet functions that
> appear to do the same job to anyone who is unaware of the subtleties
> involved.
>

If the user has an algorithm which requires one function over the other , but
is not aware of the difference between them , then should they really should
not be writing anything that sophisticated. Either of the new functions would
be better than the old one in any case.

> I would personally prefer to call this a test:
>
> mpz_prime_test(mpz_t n, enum alg, uint trials) + rand_state?
>
> to avoid potentially confusing names.
>
> I am also uneasy about returning true for something that might be
> false even if we do represent this uncertainty in the name.
>
> How about this:
>
> mpz_is_composite(mpz_t n) that returns 1 if composite or 0 if the
> test fails (compositeness undetermined).

This may well be how I will implement it , with mpz_practical_prime being a
macro on top of it. I just did it this way as that is how it is usually
presented.Some books do point out that it would be better to call probable
prime tests , composite tests instead. If we do the composite test instead
then we can return more than just true or false , we could return a "why" ,
ie a trial divisor or a witness.

[Cactus]

On Sep 4, 3:17 pm, Jason Moxham <ja...@njkfrudils.plus.com> wrote:
> On Friday 04 September 2009 08:33:01 Cactus wrote:
>
> > On Sep 4, 4:58 am, Bill Hart <goodwillh...@googlemail.com> wrote:
> > > I don't personally like the name mpz_practical_prime_p(). The reason is
> > > that it doesn't mean anything particular to anyone but us.
>
> > I also doubt that it will help to have two differenet functions that
> > appear to do the same job to anyone who is unaware of the subtleties
> > involved.
>
> If the user has an algorithm which requires one function over the other , but
> is not aware of the difference between them , then should they really should
> not be writing anything that sophisticated. Either of the new functions would
> be better than the old one in any case.

Nevertheless I think we should avoid names that are easily
misunderstood and I would initially take this name to mean that primes
are divided into two classes - 'practical primes' and 'impractical
primes' - and that this function returns a practical one - but still a
prime. But in fact it might not be a prime at all :-)

If we are going to use 'probable_prime' for the one that gives
probability bounds, why not call this 'lazy' one 'mpz_likely_prime' -
this is more accurate and will at least encourage the potential user
to ask themselves what the difference between a likely and a probable
prime is (why do these have '_p' on the end anyway?).

> >   mpz_is_composite(mpz_t n) that returns 1 if composite or 0 if the
> > test fails (compositeness undetermined).
>
> This may well be how I will implement it , with mpz_practical_prime being a
> macro on top of it. I just did it this way as that is how it is usually
> presented.Some books do point out that it would be better to call probable
> prime tests , composite tests instead. If we do the composite test instead
> then we can return more than just true or false , we could return a "why" ,
> ie a trial divisor or a witness.

That's a good additional point in favour of this solution.

I'd still prefer the macro to be 'mpz_likely_prime' though :-)

Brian

[Jason Moxham]

On Friday 04 September 2009 11:03:23 Jeff Gilchrist wrote:
> On Thu, Sep 3, 2009 at 10:51 PM, Jason Moxham<ja...@njkfrudils.plus.com>
wrote:
> > Or getting rid of the mpz_next_prime_thing all-together , cant say I like
> > it much. What do people use it for ?
>

To me , it just doesn't "fit" with the rest of the library , I can't explain
it more than that :)

> I actually use it and find it very useful. If I'm doing some kind of
> testing or other calculations on increasing primes it is very useful
> just to call that function to get the next one to work with.
>

Anyway regardless of my clearly reasoned argument above :) :) , if you find it
usefull , then thats a good enough reason to keep it/improve it.
Ideally we have some sort of state that we can pass to the nextprime
function , I suppose we could add it to MPIR now (pointer to a structure),
and we could fill in the details later.

> Right now unless you dig into the code it is hard to tell what the two
> current prime functions really do.

It should be clear in the docs what they do , just not how they do it.

> So a new defined function that
> either provides a way to specify the algorithm to use or have
> something very clearly defined would be a great benefit.

We can add specific algorithms later , it is something I plan to do , if
everyone else thinks its a good idea.
Perhaps we should set up a new directory for future extentions , where we can
thrash out the details of algorithms and interfaces. Until you actually write
and use the code in a few situations you can never be sure what is the "best"
way to do it. If we have code as well then users can give us feedback on what
really get used.

> If someone
> is trying to do work that needs to be repeatable it would be good to
> have a way for people to say, "Use MPIR with this is_prime/prob_prime
> function using these parameters"
>

The new functions are all deterministic given the same random state.

> Jeff.
>
>

[Jason Moxham]

On Friday 04 September 2009 15:47:06 Cactus wrote:
> On Sep 4, 3:17 pm, Jason Moxham <ja...@njkfrudils.plus.com> wrote:
> > On Friday 04 September 2009 08:33:01 Cactus wrote:
> > > On Sep 4, 4:58 am, Bill Hart <goodwillh...@googlemail.com> wrote:
> > > > I don't personally like the name mpz_practical_prime_p(). The reason
> > > > is that it doesn't mean anything particular to anyone but us.
> > >
> > > I also doubt that it will help to have two differenet functions that
> > > appear to do the same job to anyone who is unaware of the subtleties
> > > involved.
> >
> > If the user has an algorithm which requires one function over the other ,
> > but is not aware of the difference between them , then should they really
> > should not be writing anything that sophisticated. Either of the new
> > functions would be better than the old one in any case.
>
> Nevertheless I think we should avoid names that are easily
> misunderstood and I would initially take this name to mean that primes
> are divided into two classes - 'practical primes' and 'impractical
> primes' - and that this function returns a practical one - but still a
> prime. But in fact it might not be a prime at all :-)
>
> If we are going to use 'probable_prime' for the one that gives
> probability bounds, why not call this 'lazy' one 'mpz_likely_prime' -
> this is more accurate and will at least encourage the potential user
> to ask themselves what the difference between a likely and a probable
> prime is (why do these have '_p' on the end anyway?).
>

Ok , I couldn't really think what to call it , calling it mpz_prime_p is an
abuse of the word prime. Calling it mpz_probable_prime_p also implies that it
satisfies the mathematical definition of a "probable prime". As long as there
is no existing definition that could be confused with it.

_p on the end to match existing , indicates returned result is a "boolean" and
so we dont need to call it "mpz_is_prime" but "mpz_prime_p"

> > >   mpz_is_composite(mpz_t n) that returns 1 if composite or 0 if the
> > > test fails (compositeness undetermined).
> >
> > This may well be how I will implement it , with mpz_practical_prime being
> > a macro on top of it. I just did it this way as that is how it is usually
> > presented.Some books do point out that it would be better to call
> > probable prime tests , composite tests instead. If we do the composite
> > test instead then we can return more than just true or false , we could
> > return a "why" , ie a trial divisor or a witness.
>
> That's a good additional point in favour of this solution.
>
> I'd still prefer the macro to be 'mpz_likely_prime' though :-)
>

fine by me

> Brian
>
>

[Bill Hart]

I also prefer the name mpz_likely_prime. No one is going to wonder what that means, it is self explanatory. 

Jason, I'm not sure we are understanding what you mean precisely by not liking the whole mpz_next_prime thing. I use it all the time and I'm pretty sure it is a really commonly used thing. Actually it returns very few composites, so it is very useful in many situations.

But I'm not 100% sure you meant get rid of any next_prime facility altogether. That would break an awful lot of code out there. Did you mean you didn't like calling it next_prime or you didn't like how it was currently being done? Or did you just mean you wanted to get rid of any such facility. I think the latter would be a very bad step. I agree it doesn't fit very well. I think the sieve idea would be more consistent with the rest of the library. But even still, many times when prototyping something you really want an mpz_nextprime_quick_dirty_no_fuss_not_too_much_typing()

Bill.

2009/9/4 Jason Moxham <ja...@njkfrudils.plus.com>

[Jason Moxham]

On Friday 04 September 2009 16:34:18 Bill Hart wrote:
> I also prefer the name mpz_likely_prime. No one is going to wonder what
> that means, it is self explanatory.
> Jason, I'm not sure we are understanding what you mean precisely by not
> liking the whole mpz_next_prime thing. I use it all the time and I'm pretty
> sure it is a really commonly used thing. Actually it returns very few
> composites, so it is very useful in many situations.
>
> But I'm not 100% sure you meant get rid of any next_prime facility
> altogether. That would break an awful lot of code out there. Did you mean
> you didn't like calling it next_prime or you didn't like how it was
> currently being done? Or did you just mean you wanted to get rid of any
> such facility. I think the latter would be a very bad step. I agree it
> doesn't fit very well.

Thats the only reason I can think of "doesn't fit" , I suppose in a perfect
world , this would be in another library you would use with MPIR and it would
provide a big bucket of prime stuff. As no such library exists and it would
break existing code then we should leave it alone.

> I think the sieve idea would be more consistent with
> the rest of the library. But even still, many times when prototyping
> something you really want an
> mpz_nextprime_quick_dirty_no_fuss_not_too_much_typing()

Functions/macros for prototyping are certainly worth having , I use them all
the time , I have just never used that particular one.

[Jason Moxham]

On Friday 04 September 2009 16:49:13 Jason Moxham wrote:
> On Friday 04 September 2009 16:34:18 Bill Hart wrote:
> > I also prefer the name mpz_likely_prime. No one is going to wonder what
> > that means, it is self explanatory.

I have changed the name to mpz_likely_prime_p , and I will do the same for the
nextprime one so that will now be mpz_next_likely_prime

Jason

[jason]

On Sep 4, 11:03 am, Jeff Gilchrist <jeff.gilchr...@gmail.com> wrote:

Hi , did you mean that results should be repeatable across different
arch's ie 64/32bit ? or just repeatable on a set arch?
For a set arch and random seed then everything is repeatable. For a
set random seed and any arch then the urandom functions (uniformly
distributed) are repeatable(or should be!!!) , the rrandom fn's are
not. The mpz_probable_prime_p fn is "not" , although this is only
because on some arch'es it may be faster to do more trial division
than on others and so if you are (un)lucky you will give the function
a number which is composite but passes the miller-rabin test but fails
the trial div test. The mpz_likely_prime_p test is optimized for speed
so has no guarentee , same for mpz_next_likely_prime_p.

Jason

[Jeff Gilchrist]

On Sun, Sep 13, 2009 at 10:25 PM, jason <ja...@njkfrudils.plus.com> wrote:

> Hi , did you mean that results should be repeatable across different
> arch's ie 64/32bit ? or just repeatable on a set arch?

A set architecture would be fine, so people could say, using arch X,
with MPIR vY.Z then using this function with this seed will give you
the following output...

> For a set arch and random seed then everything is repeatable. For a
> set random seed and any arch then the urandom functions (uniformly
> distributed) are repeatable(or should be!!!) , the rrandom fn's are
> not. The mpz_probable_prime_p fn is "not" , although this is only
> because on some arch'es it may be faster to do more trial division
> than on others and so if you are (un)lucky you will give  the function
> a number which is composite but passes the miller-rabin test but fails
> the trial div test. The mpz_likely_prime_p test is optimized for speed
> so has no guarentee , same for mpz_next_likely_prime_p.

The likely ones as you said are for speed so that is fine. It would
be good to document what you said above about arch/random seed being
repeatable or not just so people are aware in case they want to use
stuff across different platforms/archs.

Jeff.