Re: [flint-devel] Simultaneous Sieving and Trial factoring or Pocklington

[Bill H. <goo...@go...>]

Holy moly!! That was quick work. I thought it would take you at least
a week to write that code. That's amazing.

I only just figured out the best hash function to use last night, and
it is precisely the one you chose. Well done!

The idea I had doesn't work I think. It was basically this:

Suppose we want 2^K mod n1, n2, ..., nr

where n1, n2, ..., nr are all relatively close together (and so in our
case coprime).

My thought was to first compute A = 2^K mod n1*n2*....*nr using
multiprecision arithmetic.

Now we get 2^K mod n1*n2*...n{r/2} and 2^K mod n{r/2+1}*...*nr

simply by reducing A modulo both of the smaller products.

We keep splitting the products into two (recusively), until we are
finally getting 2^K mod n1, n2, ...., nr.

This definitely won't work with ordinary GMP division however, since
it uses an algorithm which is asymptotically too slow (O(M(n)log(n))
where M(n) is the time taken to do a multiplication. However, FLINT
has some code for Montgomery multiplication in fmpz.c/h which gets rid
of that extra log factor in precisely this situation. I can't recall
if we already implemented reduction modulo a whole pile of n's using
montgomery multiplication yet or not. If it is there, it is exactly
what you need. If not, I have to implement it anyway.

But, I'm still not convinced my idea works anyway. We could try it I
suppose. But I think I convinced myself yesterday it will actually be
slower than computing the individual 2^K mod ni's

Bill.

2008/8/5 Peter Shrimpton <ps...@gm...>:
> Hello Bill
>
> I have written some code to sieve and factor simultaneously
>
> sievefact.c sieves a chunk of numbers and uses the trial devision to factor
> n-1 for all n that get through the sieve. It uses a hash table to reduce the
> storage space required with the hash function being the 2nd to last 4 bits.
> (The last bit is alway the same). This seams to work very well indeed.
>
> sievfact2.c simultaneously sieves and checks to see if it can find a b such
> that gcd(b^((n-1)/p)-1,n)=1. It uses the same code as sievefact.c but it
> doesn't store the factors, only the cofactor. This could be useful if the
> Pocklington test is quicker then the pseudoprime tests the only trouble
> being to then decide which numbers to do the pseudoprime tests on to find a
> counter example to the Baillie-PSW test.
>
> Would it be possible for you to explain your idea about calculating powers
> of 2 mod N for lots of different numbers at once again? I can't quite
> remember exactly how it was to be done or how we could go about splitting
> the powers up once we had calculated the power of the product. An
> explanation in an email should suffice.
>
> I have also written a program that uses the list I emailed you before to
> look for counter examples to the Baillie-PSW test below 2^63. Unfortunately
> there weren't that many products in the list that were less then2^63 and I
> didn't find any counter examples. Maybe it could be worth implementing a
> Baillie-PSW test in fmpz's and having another go?
>
>
> Peter
>
> -------------------------------------------------------------------------
> This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
> Build the coolest Linux based applications with Moblin SDK & win great
> prizes
> Grand prize is a trip for two to an Open Source event anywhere in the world
> http://moblin-contest.org/redirect.php?banner_id=100&url=/
> _______________________________________________
> flint-devel mailing list
> fli...@li...
> https://lists.sourceforge.net/lists/listinfo/flint-devel
>
>