n512 := 26066645293949051030719592905562956135330228107469961043942513269914842\ 483484929237964679620381006081104118891860849212268204134097143119166213\ 304570371773919690053665661392234962224627734952928135496691891852242493\ 101341744671293374470688100773174620495254334778601125923062888673322340\ 4213064415720576165169: evalf(log[2](n512)); n768 := 73506453596461621085950995635332391848847169918534649357262147888186348\ 431371640018603064890839586344017692596023923507305466348432226209929625\ 327120849544021823313649663239999605740350179604019018717612919365208249\ 986552163241439306374113490121271580497396942623012567599272847418855029\ 270607845298465376898629980569318979953395058857899878081808746033685079\ 461863573328248877341098953931604645777360376801279914964879837772340175\ 304662768279343734815372776395473: evalf(log[2](n768)); n1024 := 63588955658330347022085230845576212298322127728777903916429075860849290\ 711328455142085797721576720292498442415284885037290996033020681533362294\ 494752164700377079645016790442513082819414542669790929668222148064727832\ 663001711071029154045794996236819848774213121764609344365772055561098385\ 185509980861530091962523838987009868994997764555809014509194221314006479\ 978167719335773901423256287889635007056554334449723329407823136742755751\ 869134095499543980287744695032261686400749081811270662576723610451504484\ 646395380593262420570124238308875102402123685071832322542397275128352595\ 49723357647718327998754795646911307672321: evalf(log[2](n1024)); BBS := proc(k::posint,seed::posint) local x,g,T,i,j,l,m,n,q,z,t; if type(procname,indexed) then l := op(procname) else l := 512; fi; if l=32 then m := 10; n := 18446414487239353729; elif l=48 then m := 11; n := 79228162474884299504590734913; elif l=64 then m := 12; n := 340282366920910821054273642375418145089; elif l=512 then m := 10; n := n512; elif l=768 then m := 10; n := n768; elif l=1024 then m := 11; n := n1024; else error "prime bit length must be 32, 48, 64, 512, 768 or 1024"; fi; if seed <= 1 or seed >= n-1 then error "seed must be in the range 1 < seed < n-1"; fi; # Note the following should never happen; it means that someone # ``guessed'' the factorization of n = p q which is extremely unlikely if igcd(seed,n)>1 then seed := seed+1; fi; # Don't allow x0 be small e.g. 2, 3, because squaring will # preserve the parity of x until x becomes bigger than n. # Also, squaring x at least once ensures that x_0 is in QR(x) x := seed; while x < n do x := x^2 od; x := irem(x,n); T := Array(0..2^m-1); # m random bits at a time for i from 0 to 2^m-1 do t := i; T[i] := seq(irem(t,2,'t'), j=1..m) od; if k = m then subs( 'L' = 2^m, proc() x := irem(x^2,n); T[irem(x,L)]; end ); else z := [0$k]; subs({'K' = k, 'L'=2^m}, proc() z := z[k+1..-1]; while nops(z) < k do x := irem(x^2,n); z := [op(z),T[irem(x,L)]]; od; op(1..k,z); end); fi; end: