Conference rusure::math

        Let n be

    336483746736483413430948239482309432473023049830498320948302948329489387
        
        Then 2^(n - 1) modulo n is

    120212827605943537765550753397510299095605896225725456103892441459772594

	If n were prime, the result would have been 1, therefore
	n is not prime.

	Dan

	p.s.  I used VAX LISP V3.0-A bignum arithmetic.  Someone
	else may wish to confirm, for example, with MAPLE.

>	p.s.  I used VAX LISP V3.0-A bignum arithmetic.  Someone
>	else may wish to confirm, for example, with MAPLE.

Want to publish the algorithm (in some dialect more transparent, perhaps,
than LISP)? We can't deal with 2^n directly for that large an n, so need
to have a more arcane way of dealing with the problem. 

	Since I didn't need anything optimized, I just took the
	"obvious O(log exp)" approach ...

	To compute:  Base^Exponent modulo Modulus

	Let:  a = 1, b = Base, e = Exponent

	Note that:  a * (b^e) = Base^Exponent mod Modulus = the answer

	So you keep changing a, b, and e so that the above relationship
	is preserved ... then when e has been reduced to 0, b^e is 1 and
	a * (b^e) is a ... which if you preserved the relationship will
	the answer.

	If e is 2k, then a * (b^e) = a * (b^2k) = a * (b^2)^k.  Now
	making the changes a -> a, b -> b^2, e -> e/2 allows b to grow
	way too large ... so you do

		a -> a
		b -> b^2 mod Modulus
		e -> k                   (where e = 2k)

	This will maintain the relationship a * (b^e) = the answer.

	If e is odd, e = 2k+1, then a * (b^e) = a * (b^(2k+1))
	= a * b * b^2k = (a * b) * (b^2)^k, so you do

		a -> a * b mod Modulus	(the order of the first)
		b -> b^2 mod Modulus	(two steps matters!)
		e -> k			(where e = 2k+1)

	So without trying to speed it up further you end up with
	something like

	Power(Base, Exponent, Modulus) {
		a = 1 ; b = Base ; e = Exponent ;
		if (e < 0) then error("I don't do inverses!") ;
		while (e > 0) {
			if (odd(e)) a = (a * b) mod Modulus ;
			b = (b * b) mod Modulus ;
			e = e/2 ; /* truncating integer division */
		}
		return a ;
	}

	which you code in your favorite language.

	Dan

    Re: .1
    
    Dan, IXP (my own bignum code) calculates
    
    120212827605943537765550753397510299095605896225725456103892441459772594
    
    as 2^(n-1) mod n.
    
    That seems to be the same result as you got with LISP.
    
      John

MAPLE agrees. If anyone cares, the working MAPLE code is:

#  POWERMOD.MAPLE; 
# Author: Lynn Yarbrough Dec 1989
#======================================================================
power := proc (base, exponent, modulus) local a, b, e;
	a:=1; b:=base; e:=exponent;
	while e > 0 do
		if mod (e,2) = 1 then a:= mod(a*b, modulus); fi;
		b := mod (b*b, modulus);
		e := trunc(e/2);
	od;
	a
end;

        The relevant theorem here is that for prime numbers p,
        if p does not divide a then a^(p-1) = 1 mod p.  (If p
        does divide a then a = 0 mod p and so a^(p-1) = 0 mod p.
        In either case though a^p = a mod p for primes p.)
        
        The number given in .0 fails this test for a=2 and so it
        is not prime.
        
        Does anybody want to factor it? :-)  I'm curious how the
        author of .0 selected it ... it wasn't divisible by any
        primes less than 100,000.  What's the probability of that
        happening? :-)
        
        Dan
        

    I suspect that the author of .0 just took 2 very large known primes and
    multiplied them together.
    
    I guess the next problem is then to factor it, right?