--- In openpfgw@yahoogroups.com,

> It only affects b^n-c forms.

On the contrary, it cripples b^n+c,
making it 3 times slower than b^n-c.

In neither case did I find any error;
just a big penalty in speed for b^n+c:

> 10^44441+299367 is 3-PRP! (154.6733s+0.0117s)
> 10^44441-285359 is 3-PRP! (58.8960s+0.0119s)

David (after 2500 tests on each form,
between 10k and 100k digits, using
Henri's database)

Why does a^b+c not use special modular reduction?

$ pfgw -V -N -q"10^10000+137"

PFGW Version 20090928.x86_Dev (Beta 'caveat utilitor')
[GWNUM 25.13]
Generic modular reduction using generic reduction
FFT length 3072 on A 33221-bit number
10^10000+137 is composite: RES64: [07495556E07307B0]
(5.7515s+0.0006s)

$ pfgw -V -N -q"10^10000-137"

PFGW Version 20090928.x86_Dev (Beta 'caveat utilitor')
[GWNUM 25.13]
Special modular reduction using
FFT length 2560 on 10^10000-137
10^10000-137 is composite: RES64: [DB780CB512A58792]
(1.6931s+0.0006s)

David

Hi
Can somebody compile pfgw for AMD processor?
Thank you.
Giovanni

--- In openpfgw@yahoogroups.com,
Mark Rodenkirch <mgrogue@...> wrote:

> I am not aware of any other bugs with PFGW at this time.
> If you find any, please let me know.

This test breaks GWNUM 25.13:

  $ pfgw -t -q"Phi(3,8^6353)/73"

  PFGW Version 20090928.x86_Dev (Beta 'caveat utilitor')
  [GWNUM 25.13]
  Detected in MAXERR>0.45 (round off check) in
  Exponentiator::Iterate
  Iteration: 38280/39691 ERROR: ROUND OFF 0.5>0.45

The -a1 switch shows that we are dealing with a PRP:

  $ pfgw -t -a1 -q"Phi(3,8^6353)/73"
  Phi(3,8^6353)/73 is PRP! (20.6874s+0.0040s)

David

This seems like a bug, not a feature. Something about this number makes WinPFGW
3.2.2 err when the -a1 option is used.

-qR(3021,160809)*10+1 -f -a1

Error occuring in PFGW at xx Oct xx xx:16:30 2009
Expr = R(3021,160809)*10+1
Failed at bit 23585 of 60213
Msg = Detected in gw_test_mismatched_sums() in prp_using_gwnum
Iteration: 23585/60213 ERROR: SUM(INPUTS) != SUM(OUTPUTS),

and

Generic modular reduction using generic reduction FFT length 7K on A 60214-bit
number
R(3021,160809)*10+1 ERROR DURING PROCESSING! (17.8084s+12.2846s)


But with other '-a' values...

-qR(3021,160809)*10+1 -f
-qR(3021,160809)*10+1 -f -a2

The results:

Generic modular reduction using generic reduction FFT length 6K on A 60214-bit
number
R(3021,160809)*10+1 is composite: RES64: [A78C20E4DD2F3BAF] (49.3246s+16.8789s)
Generic modular reduction using generic reduction FFT length 8K on A 60214-bit
number
R(3021,160809)*10+1 is composite: RES64: [A78C20E4DD2F3BAF] (63.4253s+16.3123s)

-a-1 and -a-2 also work correctly.

(and with -f1000, it finds a factor)

R(3021,160809)*10+1 has factors: 13742371

I found an interesting dark corner. For all of these numbers, PFGW 3.2.2 gives
an error (unless -a1 is used, in which case they come back as composite).  Same
result with WinPFGW and the Linux version:

R(2773,150105)*10+1
R(2774,188088)*10+1
R(2777,150105)*10+1
R(2780,152825)*10+1
R(2784,152825)*10+1
R(2787,188088)*10+1
R(2787,161019)*10+1
R(2788,188088)*10+1
R(2789,188088)*10+1
R(2793,195056)*10+1
R(2798,186198)*10+1
R(2798,150105)*10+1
R(2798,195056)*10+1
R(2800,188088)*10+1
R(2805,120102)*10+1
R(2806,120102)*10+1
R(2806,169869)*10+1

Example:
-----------------------------------------------------------------------
Error occuring in PFGW at Thu Oct  8 19:48:20 2009
Expr = R(2780,152825)*10+1
Failed at bit 177 of 55410
Msg = Detected in gw_test_mismatched_sums() in prp_using_gwnum
Iteration: 177/55410 ERROR: SUM(INPUTS) != SUM(OUTPUTS),

---- djbroadhurst <d.broadhurst@...> wrote:
>
> Phil correctly post-dicted my entirely deliberate intent :-)
>
> > I've upgraded the gwnum code to detect many of these cases
> > and choose a better modulus.
>
> Thank ye kindly, Sir!
>
> > I await the next wave of bug reports :)
>
> I shall do my best to oblige, when a new linux build appears.
>
> David (trying to be diligent)

I hope to make a Windows build available this weekend.  Once I do, I'll let
Steven know and he can build you a linux executable.

--Mark

--- In openpfgw@yahoogroups.com,
George Woltman <woltman@...> wrote:

> On Mon, Sep 28, 2009 at 12:32 PM,
> djbroadhurst <d.broadhurst@...> wrote:
>
> > Here, are two more ways of breaking gwnum:
> > $ pfgw -t -q"Phi(35737,2)"
> > $ pfgw -t -q"Phi(34585,2)"
>
> As Phil correctly speculated, these errors
> were due to non-random bit patterns that
> the FFTs hate.

Phil correctly post-dicted my entirely deliberate intent :-)

> I've upgraded the gwnum code to detect many of these cases
> and choose a better modulus.

Thank ye kindly, Sir!

> I await the next wave of bug reports :)

I shall do my best to oblige, when a new linux build appears.

David (trying to be diligent)

On Mon, Sep 28, 2009 at 12:32 PM, djbroadhurst <d.broadhurst@...> wrote:
> Here, are two more ways of breaking gwnum:
> $ pfgw -t -q"Phi(35737,2)"
> $pfgw -t -q"Phi(34585,2)"

As Phil correctly speculated, these errors were due to non-random bit
patterns that
the FFTs hate.

I've upgraded the gwnum code to detect many of these cases and choose
a better modulus.  Specifically, gwnum multiplies the input number by
odd numbers less than 1000.  If the multiplied number, treated as an array
of 32-bit values, consists of 25% or more zero or minus one then gwnum
operates modulo this multiplied number.  This seems to reduce the round off
error.

I've tested the modified code on all the examples.  Only Phi(35737,2) case
still fails - gwnum does not find a suitable multiplier.

The unrelated error with -a2 is fixed.  Simply an over-aggressive ASSERT.

The 25.13 source code has been uploaded.  I await the next wave of bug
reports :)

---- George Woltman <woltman@...> wrote:
> Hi Mark,
>
> On Tue, Sep 29, 2009 at 9:26 AM,  <mgrogue@...> wrote:
> >
> > pfgw -a1 -t -q"Phi(82730,2)"
> >
> > Primality testing Phi(82730,2) [N-1, Brillhart-Lehmer-Selfridge]
> > Running N-1 test using base 2
> > N-1: Phi(82730,2) 1/34213 mro=0
> > Iteration: 29/34213 ERROR: SUM(INPUTS) != SUM(OUTPUTS),
>
> As Phil speculated, we are dealing with a number that has a nasty
> bit pattern that magnifies FFT rounding errors.  There seems to be
> three problems:
>
> 1) Can I make -a0 work properly?  Maybe.  I'll work on that today.
> 2)  Why did we get the -a2 ASSERT?  I've not investigated yet, though it
> is probably harmless.
> 3)  The -a1 sum(inputs) != sum(outputs) above.
>
> Even when using a -aN switch, the number still has a nasty bit pattern
> which increases roundoff errors.  While we don't get near the fatal
> 0.5 roundoff, we do get larger than expected roundoffs in the
> sum(inputs) != sum(outputs) sanity check.
>
> My recommendation for the -aN cases is that pfgw should increase
> gwdata->MAXDIFF.   The theory being the user may have selected
> the -aN option because he is testing a pathological number.  To me,
> this makes better sense than our two other options:  a)  A separate
> command line argument to increase MAXDIFF (too confusing to the
> end user) or b) gwnum tries to detect these nasty bit patterns and
> automatically increase MAXDIFF (I might miss some cases).
>
> If you agree, I recommend adding this line of code wherever -aN is used:
>         gwdata->MAXDIFF *= 1000.0;
> I tested the case above with multiplying by 10.0 and it worked OK.
>
> Comments?

I have added that after calling gwset_square_carefully_count(). Here is the new
output using -a1 and -tc:

Primality testing Phi(82730,2) [N-1/N+1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
Running N-1 test using base 3
Running N-1 test using base 7
Running N+1 test using discriminant 23, base 1+sqrt(23)
Phi(82730,2) is Fermat and Lucas PRP! (50.6017s+0.0299s)

--Mark

Hi Mark,

On Tue, Sep 29, 2009 at 9:26 AM,  <mgrogue@...> wrote:
>
> pfgw -a1 -t -q"Phi(82730,2)"
>
> Primality testing Phi(82730,2) [N-1, Brillhart-Lehmer-Selfridge]
> Running N-1 test using base 2
> N-1: Phi(82730,2) 1/34213 mro=0
> Iteration: 29/34213 ERROR: SUM(INPUTS) != SUM(OUTPUTS),

As Phil speculated, we are dealing with a number that has a nasty
bit pattern that magnifies FFT rounding errors.  There seems to be
three problems:

1) Can I make -a0 work properly?  Maybe.  I'll work on that today.
2)  Why did we get the -a2 ASSERT?  I've not investigated yet, though it
is probably harmless.
3)  The -a1 sum(inputs) != sum(outputs) above.

Even when using a -aN switch, the number still has a nasty bit pattern
which increases roundoff errors.  While we don't get near the fatal
0.5 roundoff, we do get larger than expected roundoffs in the
sum(inputs) != sum(outputs) sanity check.

My recommendation for the -aN cases is that pfgw should increase
gwdata->MAXDIFF.   The theory being the user may have selected
the -aN option because he is testing a pathological number.  To me,
this makes better sense than our two other options:  a)  A separate
command line argument to increase MAXDIFF (too confusing to the
end user) or b) gwnum tries to detect these nasty bit patterns and
automatically increase MAXDIFF (I might miss some cases).

If you agree, I recommend adding this line of code wherever -aN is used:
         gwdata->MAXDIFF *= 1000.0;
I tested the case above with multiplying by 10.0 and it worked OK.

Comments?

Regards,
George

---- djbroadhurst <d.broadhurst@...> wrote:
> --- In openpfgw@yahoogroups.com,
> Mark Rodenkirch <mgrogue@...> wrote:
>
> > I don't understand why you are pushing for a new build
> I should like to have a version free of all order dependence
>
> > when you know that it will still have issues.
> Then the remaining issues would be free of order dependence.
> But you are the boss, Mark. So it's quite in order to say no.

Just to be clear that we aren't talking Apples and Dells, there are two separate
order dependence issues.  The first is the random number generator used in
gwnum.  The second is the bug you identified this week with primality testing. 
The first was fixed in 3.2.2, the second is fixed in 3.2.3, but I am awaiting
assistance from George so that the other issues identified in 3.2.2 (which
appear to be in gwnum) will be included in the official 3.2.3 release.

If there will be a significant delay from George (and I doubt that there will
be), then I could release a 3.2.3 this week and release a 3.2.4 after the other
issues are resolved.

I apologize for this delay as it affects your testing, but I think that we can
agree that you would like to test a version with no known bugs.

--Mark

--- In openpfgw@yahoogroups.com,
Mark Rodenkirch <mgrogue@...> wrote:

> I don't understand why you are pushing for a new build
I should like to have a version free of all order dependence

> when you know that it will still have issues.
Then the remaining issues would be free of order dependence.
But you are the boss, Mark. So it's quite in order to say no.

David

I have modified PFGW to do the following when a roundoff/sumout/mismatched sums
error occurs during a primality test:

pfgw -t -q"Phi(82730,2)"

Primality testing Phi(82730,2) [N-1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
N-1: Phi(82730,2) 5000/34213 mro=0
Iteration: 6821/34213 ERROR: ROUND OFF 0.5>0.45
   (Test aborted, try again using the -a1 switch)
Phi(82730,2) is unknown (2.8938s+0.0050s)


pfgw -a1 -t -q"Phi(82730,2)"

Primality testing Phi(82730,2) [N-1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
N-1: Phi(82730,2) 1/34213 mro=0
Iteration: 29/34213 ERROR: SUM(INPUTS) != SUM(OUTPUTS),
   (Test aborted, try again using the -a2 (or possibly -a0) switch)
Phi(82730,2) is unknown (1.9855s+0.0067s)


Oddly enough -a2 fails with an error in gwnum (see below).   George, could you
investigate?  The changes I have made to this point have been committed.

pfgw -a2 -t -q"Phi(82730,2)"

Primality testing Phi(82730,2) [N-1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
Assertion failed: * addr (gwdata, s, gwdata->FFTLEN/2-1) > -2.0 && * addr
(gwdata, s, gwdata->FFTLEN/2-1) <= 0.0, file gwnum.c, line 6787


-a, -a1, and -a2 work for Phi(12365,2).

I also fixed a separate error where PFGW would return PRP instead of "unknown"
under some conditions where one of these errors would occur.  I will not release
a new build of PFGW (for any platform) until George and I have a resolution on
this -a2 issue.

--Mark

--- In openpfgw@yahoogroups.com,
Mark Rodenkirch <mgrogue@...> wrote:

> George's new random number logic is in PFGW 3.2.2.

A fortiori, this recent Windoze build:
http://openpfgw.svn.sourceforge.net/viewvc/openpfgw/pfgw_win_3.2.3_20090928.zip
should be now free of *all* order-dependence, not so?
If so, it would be both a kindness and courtesy to provide
an equally order-independent linux build of version 3.2.3.

David

--- In openpfgw@yahoogroups.com,
Mark Rodenkirch <mgrogue@...> wrote:

> It is possible that the build you have was built with
> the current version of that file, but I need to investigate.

That is of no account, since mt19937.c would be vitiated by
the indubitable order dependence on bases in the version of
August 18. Conversely, a new linux patch of the base problem
would be vitiated by an absence of mt19937.c.

The situation is clear: until there is a version with *both*
mt19937.c and reproducible bases, beta-testing is *very*
difficult. Until there is *linux* version with both, it is
very difficult for *me* to help George.

Yrs for aye

David

--- In openpfgw@yahoogroups.com,
Mark Rodenkirch <mgrogue@...> wrote:

> IIRC, primality tests ignore the -a switch.

Not so.

The switch -a1 will avoid the errors that I have
reported. Videlicet:

$ pfgw -tc -a1 -q"Phi(13,2^2749)/8191"

> Phi(13,2^2749)/8191 is Fermat and Lucas PRP!

Yet without -a1, version 3.2.2 fails:

$ pfgw -tc -q"Phi(13,2^2749)/8191"

> Expr = Phi(13,2^2749)/8191
> Failed at bit 3 of 32974

Note that the wise PrimeMogul uses the -a1 switch.

However, if Mark merely makes -a1 mandatory for -tc,
then George's "carefully" will be let of the hook,
whereas it would be much better, in my opinion,
if George were to reconsider "carefully" in the
light of my diligent findings.

Practice maketh perfect...

David

--- In openpfgw@yahoogroups.com,
Mark Rodenkirch <mgrogue@...> wrote:

> Steven can grab at any time and produce a build if he wants

That would be helpful, please, if (and only if)
it is compiled with George's mt19937.c file.

Then we will be left with a clearly reproducible
brokenness of gwnum and George can ignore all the
rest of this complicated history, when he gets his
laptop back.

It seems a good idea to mend what you can,
the better to let others break what we do
yet understand.

David