# [Tutor] Actual code that illustrates problem

Danny Yoo dyoo at hkn.eecs.berkeley.edu
Thu Aug 17 18:57:40 CEST 2006

```
> To try to find factors of z, using w.
>
>>>>
>
> * What are the inputs? What is 'z', and what is 'w'?
>
> ******
>
> z is the number to be factores.
>
> w is a "witness", a number that may help find the factors of z.

[My apologies in advance; this message is a bit long.]

Hi Kermit,

Ok, good.  You should add this as a comment to the function's header, so
that other people can see this.  Here is an example:

def strongfac(z, w):
"""z is the number to be factored.
w is a witness that may help find the factors of z.
"""
## rest of function body.

At the very beginning of the function body, we're allowed to make a string
that acts as function documentation.  Python programmers expect this kind
of "documentation string" at the head of a function, so that they're
prepared for what comes next.

> * What are the outputs? What is the return value of strongfac?
>
> The output is the return value of strongfac.
> fac = [ x, y, difficulty of factoring z using w]
> or
> fac = [0,0,0] if strongfac could not factor z using w.

Great!  Ok, I'm assuming that 'x' and 'y' are two arbitrary factors of
'z'.  Are there other properties about x and y that you want to state,

At this point, I'm distilling what you've said into a documentation
string:

def strongfac(z, w):
"""strongfac: number number -> [x, y, difficulty]

Factors z into two pieces, returning those two pieces as well as the
difficulty in factoring z.  w is a witness that may help find the
factors of z.

If no factors can be found, returns [0, 0, 0].
"""
## rest of function body.

Does this make sense so far?  The point is to make it easy for humans to

>> # face = [x,y,0]
> [some code cut]
>> # face[0] = x
>> # face[1] = y
>> # face[2] = 0
>
>> The three assignments to face[0] through face[2] don't do anything
>> effective and clutter the code.
>
> In fact, I knew that.  I inserted it in an attempt to overide the
> apparent bug that I saw.
>
> Sometimes it worked.

This is a bad sign.  It should not have worked.  *grin*

Next time you hit something mysterious like this, mention it to the list.
It'll be a good puzzle for the others here to take a look at.  Your code
should be as rational as possible.  Don't just add code in hoping that
it'll fix some problem: try to understand why it's not working first.
Look for root causes.

>> In fermat(), there are magic numbers:
> [cut]
>> These seem pretty arbitrary. Can you explain them?

> Yes.  These are limits of ranges.  I had not yet evolved the module to
> replace the range limits with parameters.

> Have you considered breaking those out as independent helper functions?
>
> I have considered it.

Consider it more strongly.  *grin*

like this:

#################################################################
def strongfac(z,w):
x = gcd(z,w-1)
if x > 1:
if x < z:
y = z/x
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:
return [x,y,0]
## other tests
################################################################

(I'm trimming out the print statements just to keep this small.)

Those two tests, the P-1 and square=square tests, can be broken out into
two separate functions.  Let's see what this might look like:

############################################################
def check_p_minus_1(z, w):
"""Checks to see if z can be factored by the P-1 Method.
If so, returns [x, y, 0]; otherwise, returns [0, 0, 0].
"""
x = gcd(z,w-1)
if x > 1:
if x < z:
y = z/x
return [x,y,0]
return [0, 0, 0]
############################################################

This "refactoring" allows us to look at check_p_minus_1's action in
isolation, and also makes it easier to ask questions like: what happens if
x > z?  Is it really possible that the return value from gcd() is bigger
than the initial inputs to gcd()?  (As far as I understand gcd(), NO!)

So this refactoring is useful just as a matter of letting someone just
look at a small bit of code and understand it completely.  As far as I can
understand, check_p_minus_1() should work even if it's simplified to:

##########################
def check_p_minus_1(z, w):
x = gcd(z, w-1)
if x != 1:
return [x, z/x, 0]
return [0, 0, 0]
##########################

Anyway, once we break out the P-1 check out into a separate function, we
can rewrite strongfac() to use check_p_minus_1():

################################
def strongfac(z, w):
face = check_p_minus_1(z, w)
if face != [0, 0, 0]:
return face
## ... other tests here
################################

Can you try this?  Can you try breaking out the square=square test in a
similar way to how I treated the check_p_minus_1() code?

The high level goal here is to turn strongfac() into a very simple looking
function.  In pseudocode, it'll look something like:

############################
def strongfac(z, w):
use check_p_minus_1 test and return if it succeeds
use square=square test and return if it succeeds
...
############################

This will make strongfac very regular to read.  It'll also make it much
easier to trace why one of your return values isn't returning what you
want.
```