[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

1168.0. "is it or not a prim" by RIPPLE::ABBASI_NA () Thu Dec 21 1989 21:17

    something to work at over the xmas holidays
    
    is this number a prime ?
    
    336483746736483413430948239482309432473023049830498320948302948329489387
    
    if you say Yes then prove it, if you say no then also prove it..
    
    
    
    
T.RTitleUserPersonal
Name
DateLines
1168.1AITG::DERAMODaniel V. {AITG,ZFC}:: D'EramoThu Dec 21 1989 22:2715
        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.
1168.2Well, not on a uVAXII, at leastAKQJ10::YARBROUGHI prefer PiFri Dec 22 1989 13:466
>	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. 
1168.3the variables must still all be "bignums"AITG::DERAMODaniel V. {AITG,ZFC}:: D'EramoFri Dec 22 1989 14:3048
	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
1168.4CompositeVMSDEV::HALLYBThe Smart Money was on GoliathFri Dec 22 1989 15:4111
    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
1168.5Yup.AKQJ10::YARBROUGHI prefer PiFri Dec 22 1989 18:2514
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;
1168.6AITG::DERAMODaniel V. {AITG,ZFC}:: D'EramoSat Dec 23 1989 00:5015
        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
        
1168.7DWOVAX::YOUNGHistory punishes the late - MGSun Dec 24 1989 04:554
    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?