[Tutor] Actual code that illustrates problem

[Alan Gauld]

While others have made good suggestions to clarify the code I thought
I'd try to tackle the question of whether we had a bug in Python.

Unfortunately the debug output does not come from the code that's
posted so its difficult to figure out what's been happening.

For example, one apparently good and one "faulty" test:

>  In strongfac
>  Found1: x =  53799857
>  Found1: y =  1858741
>  face =  [53799857L, 1858741L, 0]
>  Found1: factor by strong probable prime test, using witnes 
> 15306543515214

Note the mis-spelling of witnes(sic) - it does not appear in the code!

>  Found1: factors are  53799857 1858741
>  Found1: returning  [53799857L, 1858741L, 0]  to fermat routine.
>  Retrieved from strongfac, face =  [0, 0, 0]
>  In fermat: k =  13  x =  0  y =  0  face =  [0, 0, 0]

Similarly the first line has the text "factors are 53..."

But in the code all instances of "factors are" are followed by the 
word "by"

So I conclude the tests are not from this code. The fault may be in 
this code
but I can't be sure...

However a couple of observations might help:

> #    def strongfac(z,w):
> #        x = gcd(z,w-1)
> #        if x > 1:
> #            if x < z:

You can simpliffy this 2 stage test using either boolean operartors:

if x > 1 and x < z:

OR, almost uniquie to pyhon:

if 1 < x < z:

That removes one whole layer of indentation.
This trick can be applied in many places in the algorithm.


Also


> #                y = z/x
> #                print "Found factors by P-1 Method as part of 
> Strong
> probable prime test, using witness",w,"."
> #                print " x = ",x," y = ",y
> #                return [x,y,0]
> #        w2 = (w * w)%z
> #        s = ksqrt(w2)
> #        if w2 == s * s:
> #            if s != w:
> #                x = gcd(z,kabs(w2 - s))
> #                if x > 1:
> #                    if x < z:
> #                        print "Found factors by square = square as 
> part of
> Strong probable prime test, using witness",w,"."
> #                        return [x,y,0]

If x was not between 1 and z in the first test y is not defined at 
this point.

> #        trace = 0
> #        t = z - 1
> #        a = 0
> #        while t%2 == 0:
> #            t = t/2
> #            a = a + 1
> #        test = pow(w,t,z)
> #        if test ==1:
> #            x = gcd(z,w-1)
> #            if x > 1:
> #                if x < z:
> #                    y = z/x
> #                    print " Found factor by Strong probable prime 
> test,
>using withness ",w,"."
> #                    return [x,y,0]
> #        else:
> #            x = gcd(test-1,z)
> #            if x > 1:
> #                print " "
> #                print " In strongfac "
> #                print " Found1: x = ",x

You could do all of this with a single print:

print "\n In strongfac \nFound1: x = ", x

I won't go any further because its pointless given the discrepency 
between
the data and the code, but hopefully those pointers will be helpful in 
your
efforts to tidy the code into separate functions.

Alan G.