WARNING If you want any of your homeworks back, my office hours next Friday (May 23rd) will be the last chance to get them. I will have all homeworks that I have graded during every office hours up to and including next Friday, then they're getting shredded.

> in a negative.   Also, the notation of the modular operation is very
> confusing in the reader....when it says check if b = 1 (mod n) it is not
> saying b = 1%n it is b%n =1, so in the cases where it says compute b =
> a^r(mod n) and b = b^2(mod n) what exactly should we be calculating? (i.e.
> where do we place the % sign )
  
His notation is what mathematicians use.  

  b = 1 (mod n)

is saying test if b = 1 when you are doing mod n math.

  b = a^r (mod n)

is saying store the result of a^r into b, but you're doing mod n math.

I agree it is kinda confusing (especially the first time you see it) but  
if you take a second look at the notation, what is implied becomes clear.
Remember that this is standard notation for mathematicians; it wasn't 
cooked up just to confuse you.

> In your notes you state that 3 = -1 % 4
> In Java, ((-1) % 4) is -1.
> Am I missing something here?
  
Sorry I should say mod.  In case I do that again, I sometimes use % to    
mean a "math" modulus operator where the result of performing % n is 
between 0 and n-1 inclusive.  Neither C/C++ nor Java do this, apparently. 
I'll try to only use the word "mod" in the future.

> Do we only need to show the trace for the first composite number?
> 
> Meaning, we list all the primes we find, and just show the test for that composite number?

Exactly. Show what the program gives you for all your 10 test values.     
Note that when normally running the program, you don't always have to use
all 10 test values.

> For part QS1, the sheet says to go for x = [0, 1, -1, 2, -2...r, -r] for r ~
> 400. Is that correct? It just seems excessive since all he examples are around
> 10-60. It doesn't affect my output but seems like overkill. Let me know. Thank
> you.
  
Start small, and work your way up.  The problem with too small of a r is  
that you won't get enough rows in your table from which to build sets 
of tau.

> What can I use for large integers in C++, I have looked all over the web and I can't find anything.

http://www.google.com/custom?site=search&hl=en&lr=&ie=ISO-8859-1&safe=off&cof=&q=arbitrary+precision+library+C%2B%2B&btnG=Google+Search

> In the Miller-Rabin primality test, in the for loop, when it says if b = 
> -1(mod n) then return prime, else compute b^2(mod n)......what does it mean 
> by the compute b^2(mod n)?  Is it saying that b = b^2(mod n)?  Thank you for 
> your help.

Yup.  Store it back into b.

> I'm doing the first part of hw7 (the miller-rabin test) and ran into 
> some confusion in the algorithm... on page 8 of the
> Primality and Factorization chapter in the reader steps MR3 and MR4 state
> 
> MR3.    Compute b = a^r (modulo n)
> MR4.    if b = 1 (modulo n), then Return("prime") and END
> 
> -> since a, r, and n, are known step MR3 is straight forward
> -> but the   b = 1 (modulo n) is confusing to me..   does this mean 
> calculate euclidean(b,n) and check to see if the result is 1
> [and if so return prime] ??

All he means is compute b in MR3, and test if it's 1 in MR4. Since you 
already did mod in MR3, you don't really have to do it in MR4.  The 
operation is still there, but you don't have to do it explicitly.

> if this is so, then MR6a is even more confusing to me.  how could i 
> get a -1 for a result from the euclidean algorithm? 

For example 3 = -1 modulo 4.  There are infinitely many numbers that are 
-1 modulo n for any n.  At least I think that's the case.  So you won't 
get a negative number as a result of Euclidean, but you might get 
something that is -1 modulo n.  Hope that makes sense.  If 
not, discussion/OH will help.