On Dec 7, 1:34 am, Bill Hart <[email protected]> wrote:
> Brian,
>
> I forgot to mention, there is a new test file
> tests/mpz/t-likely_prime_p.c which you might wish to add to the
> Windows build.
>
> Bill.
>
> 2009/12/7 Bill Hart <[email protected]>:
>
> > This looks like a sensible interface. I think I would like to
> > implement something like this.
>
> > For now I have simply turned on my BPSW test for single limbs in
> > mpz_likely_prime_p and added some test code. This means at least for
> > single limbs, mpz_nextprime probably won't return any composites. Most
> > people who want an actual prime who are using this function probably
> > want a single limb prime. Others are probably going to realise that
> > multiple limb primes are not necessarily going to be prime.
>
> > Anyhow the test code passes, not that it does a whole lot. It merely
> > uses the test code for mpz_probab_prime_p which just trial divides to
> > see if a given number is prime or not, so it doesn't do anything with
> > multiple limb primes anyway.
>
> > Bill.
>
> > 2009/12/5 Case Vanhorsen <[email protected]>:
> >> On Sat, Dec 5, 2009 at 6:49 AM, Bill Hart <[email protected]>
> >> wrote:
> >>> I guess the important question is, is there a better way for us to do
> >>> mpz_nextprime and mpz_likely_prime_p.
>
> >>> I strongly suspect people who are after primes for RSA or DH
> >>> applications will use the latter, whereas someone after a convenient
> >>> function which for all intents and purposes returns a prime, will use
> >>> the former.
>
> >>> Thus my feeling is that mpz_nextprime should be more like the GMP
> >>> mpz_nextprime function, i.e. with "few" exceptions. However, this is
> >>> certainly something we should discuss. Technically the function is
> >>> obsoleted anyway because it doesn't, and wont ever, do what it says.
> >>> But even so, it will be replaced by mpz_next_likely_prime. This is
> >>> going to be a problem if mpz_likely_prime_p does something completely
> >>> different to mpz_next_likely_prime.
>
> >>> So I see a potential conflict here, and no obvious solution. Any ideas?
> >> I'm sure I missed something in the prior discussions so feel free to
> >> correct me.
>
> >> These are conflicting use cases so I think the default behavior should
> >> be the most conservative. In gmpy, I'd like to assume
> >> gmpy.next_prime(n) has the same results as "while not
> >> gmpy.is_prime(n): n+=1". If it's faster, that's great.
>
> >> Would it make sense to provide the following functions?
>
> >> mpz_trial_factor(mpz_t z, n):
> >> Perform trial factoring of z to at least limit n.
>
> >> mpz_miller_rabin(mpz_t z, n):
> >> Perform a Miller-Rabin test to base-n (possibly some trial factoring).
>
> >> mpz_bpsw_psp_p(mpz_t z):
> >> Perform the BPSW test.
>
> >> mpz_mr_psp_p(mpz_t z, gmprandstate, prob, div):
> >> Perform trial factoring to div, then prob iterations of Miller-Rabin test.
>
> >> mpz_next_mr_p(mpz_t z):
> >> Returns the next mpz that passes mpz_miller_rabin(z, 2).
>
> >> mpz_next_mr_psp_p(...)
> >> Returns the next mpz that passes mr_psp_p().
>
> >> mpz_next_bpsw_p(...)
> >> Returns the next mpz that passes mpz_bpsw_psp_p().
>
> >> Then leave the old GMP functions as is. I think the old
> >> mpz_probab_prime_p would map to mpz_mr_psp_p with a fixed random
> >> state.
>
> >> And then provide convenience functions:
> >> mpz_pseudo_prime_p and mpz_next_pseudo_prime (or mpz_psp_p and
> >> mpz_next_p) that call the appropriate functions listed above with
> >> reasonable defauls. Faster, but theoretically more likely to be wrong,
> >> versions could be called mpz_fast_psp_p and mpz_fast_next_psp_p.
>
> >> If an application wants to guarantee behavior (algorithm vs. speed vs.
> >> reliability), it would call functions in the first set. If an
> >> application just wants an answer, it would call the convenience
> >> functions.
>
> >> casevh
>
> >>> Bill.
>
> >>> 2009/12/5 Bill Hart <[email protected]>:
> >>>> I realise the statement was not precise. What I meant to suggest is
> >>>> that given a number in the range I was working with, chosen through
> >>>> some randomised process, which has already been trial factored, but
> >>>> which has non-trivial factors, what is the chance that a single
> >>>> Miller-Rabin test to a random base will not detect that the number is
> >>>> composite.
>
> >>>> Of course I should have said that the chances approach 1/4 in some
> >>>> cases. This is kind of like gutter journalism. I could have said that
> >>>> your chances of dying of swine flu approached 1 in 200. For some
> >>>> particularly poorly chosen outlier sample, it's true.
>
> >>>> Of course my application just happened to be a particularly pooly chosen
> >>>> sample.
>
> >>>> Sorry for being inaccurate.
>
> >>>> By the way, on T.R. Nicely's page he has a paper on instances where
> >>>> the GMP primality test function returns composites. It does happen, it
> >>>> is just exceptionally rare. In our case it does happen, it's just not
> >>>> rare. (For some suitably vague definition of rare.)
>
> >>>> Bill.
>
> >>>> 2009/12/5 Xilman <[email protected]>:
>
> >>>>> On Dec 4, 5:29 pm, Bill Hart <[email protected]> wrote:
> >>>>>> Whoah, it just does trial division up to 1000 then uses a *single*
> >>>>>> *random* base for a strong pseudoprime test!
>
> >>>>>> I have a definite problem with this. What is the probability of
> >>>>>> returning a composite? Assuming the factors are bigger than 1000, it
> >>>>>> is like 1/4.
>
> >>>>> Your question is ill-defined and your answer is, arguably, very rarely
> >>>>> correct.
>
> >>>>> If you meant to ask: "what is the probability of a composite integer c
> >>>>> picked uniformly at random from the range 1000<c<N being reported as
> >>>>> pseudoprime by a single Miller-Rabin test?", the answer is "very
> >>>>> small, much much smaller than 1/4". The precise value of "very small"
> >>>>> depends on N, and becomes smaller as N increases.
>
> >>>>> If you meant to ask: "given that composite c < N is reported as
> >>>>> pseudoprime by a Miller-Rabin test to a particular base b, what
> >>>>> fraction of bases 2 <= b < N-1 give such a report?" the answer is "
> >>>>> less than 1/4, but a small fraction of such c give a fraction which
> >>>>> approaches arbitrarily close to 1/4 as N grows arbitrarily large".
>
> >>>>> For numbers of interest to, say, RSA or DH implementations a single M-
> >>>>> R test is sufficient as this corresponds to the first re-phrasing of
> >>>>> your question.
>
> >>>>> Paul
>
> >>>>> --
>
> >>>>> You received this message because you are subscribed to the Google
> >>>>> Groups "mpir-devel" group.
> >>>>> To post to this group, send email to [email protected].
> >>>>> To unsubscribe from this group, send email to
> >>>>> [email protected].
> >>>>> For more options, visit this group
> >>>>> athttp://groups.google.com/group/mpir-devel?hl=en.
>
> >>> --
>
> >>> You received this message because you are subscribed to the Google Groups
> >>> "mpir-devel" group.
> >>> To post to this group, send email to [email protected].
> >>> To unsubscribe from this group, send email to
> >>> [email protected].
> >>> For more options, visit this group
> >>> athttp://groups.google.com/group/mpir-devel?hl=en.
>
> >> --
>
> >> You received this message because you are subscribed to the Google Groups
> >> "mpir-devel" group.
> >> To post to this group, send email to [email protected].
> >> To unsubscribe from this group, send email to
> >> [email protected].
> >> For more options, visit this group
> >> athttp://groups.google.com/group/mpir-devel?hl=en.
Thanks Bill, I'll get up to date today.
On the interface to prime testing, the next_prime versions need a
persistent sieve structure for fast trial division up to some limit
between calls to the prime test function.
If we want to avoid passing round a structure for this, we might
consider an interface along the lines
next_prime(start_prime, prime_sieve_limit, prime_test_function,
times_to_apply_it)
Brian
--
You received this message because you are subscribed to the Google Groups
"mpir-devel" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/mpir-devel?hl=en.
