\mnb150ÿ{\rtf1\ansi\deff0\deftab720{\fonttbl{\f0\fswiss MS Sans Serif;}{\f1\froman\fcharset2 Symbol;}{\f2\fswiss\fprq2 System;}{\f3\fmodern\fprq1 Courier New;}{\f4\froman\fprq2 Times New Roman;}} {\colortbl\red0\green0\blue0;\red255\green0\blue0;\red0\green0\blue255;} \deflang1031\pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs22\cf1 {\pntext\f1\'b7\tab}reset(): \par \pard\li600\ri1\fi-300\plain\f3\fs22\cf1 _mod := mods: \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs22\cf1 {\pntext\f1\'b7\tab}// Return a list of all indices of a table. \par \pard\li600\ri1\fi-300\plain\f3\fs22\cf1 indices := proc( t:DOM_TABLE ):DOM_LIST \par begin \par map( [op(t)], op, 1 ); \par end_proc: \par protect(indices): \par \par // Return a list of all entries of a table. \par entries := proc( t:DOM_TABLE ):DOM_LIST \par begin \par map( [op(t)], op, 2 ); \par end_proc: \par protect(entries): \par \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs22\cf1 {\pntext\f1\'b7\tab}dixon := proc(N,B) \par \pard\li600\ri1\fi-300\plain\f3\fs22\cf1 local gamma, A, a, alpha, b, bs, factorbase, g, h, i, AA, p, rnd, s, sol, t, x; \par begin \par /* this is a meaningless long comment (delete it) */ \par // this is a meaningless short comment (delete it) \par factorbase := table(); \par p := 2; \par while p<=B do \par factorbase[p]:=TRUE; \par p := nextprime(p+1); \par end_while; \par factorbase := indices(factorbase); \par h := nops(factorbase); \par A := table(); \par rnd := random(2..N-2); \par while nops(A) <= h do \par b := rnd(); \par g := igcd(b,N); \par if g>1 then \par next; // Use this to skip early termination. \par return([g]); \par end_if; \par a := b^2 mod N; \par alpha := table(); \par for p in factorbase do \par alpha[p] := 0; \par while a mod p=0 do \par a := a/p; \par alpha[p] := alpha[p]+1; \par end_while; \par end_for; \par if a=1 then \par A[b] := alpha; \par else \par end_if; \par end_while; \par bs := indices(A); // order in bs is IMPORTANT from now on. (Why?) \par AA := Dom::Matrix(Dom::IntegerMod(2))([ \par [ A[b][p] $ b in bs ] \par $ p in factorbase \par ]); \par sol := linalg::matlinsolve( AA, AA::dom(nops(A),1) ); \par // \par // Pick the first of the vectors spanning the kernel of AA. \par x := sol[2][1]; \par // \par // Forget that it's mod 2. \par x := Dom::Matrix()(x); \par gamma := table(); \par for p in factorbase do \par gamma[p] := _plus( x[i] * A[bs[i]][p] $ i=1..nops(A) ) / 2; \par end_for; \par s := _mult( bs[i] ^ x[i] $ i=1..nops(bs) ) mod N; \par // ...should do the "mod N" more often... \par t := _mult( p ^ gamma[p] $ p in factorbase ) mod N; \par g := igcd( s+t, N ); \par if g = 1 or g = N then return(FAIL); end_if; \par g; \par end_proc: \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs22\cf1 {\pntext\f1\'b7\tab}// This might be helpful... \par \pard\li600\ri1\fi-300\plain\f3\fs22\cf1 print( NoNL, "+" ): \par print( NoNL, "-" ): \par \pard\li50\ri6\plain\f3\fs22\cf2\protect +- \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs22\cf1 {\pntext\f1\'b7\tab}N := 41*2003; \par \pard\li50\ri6\plain\f3\fs22\cf2\protect {\pict\wmetafile8\picw1411\pich827\picwgoal799\pichgoal468 0100090000033301000005001C0000000000050000000B0200000000050000000C023B03830503 0000001E00030000001E00050000000C02D5012003050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C0000009D110AD250EC1200B8A4F177C1A4F1772030F377041766B2040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB0210FF0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377041766B2040000002D0103000B0000 0026060F000C004D6174685479706500007B000500000009020000FF0007000000210501003800 3B016400070000002105010032003B01DC00070000002105010031003B01540107000000210501 0032003B01CC01070000002105010033003B01440208000000FA02000000000000000000000400 00002D01040004000000F001000007000000FC020000FFFFFF000000040000002D010000040000 00F00101001C000000FB021000070000000000BC02000000000102022253797374656D00008515 0A2050EC1200B8A4F177C1A4F1772030F377041766B2040000002D010100040000002701FFFF04 000000F001020004000000F0010300040000002701FFFF030000000000 }\plain\f3\fs22\cf2\protect \par \pard\li50\ri2\plain\f3\fs22\cf2\protect \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs22\cf1 {\pntext\f1\'b7\tab}N := 1845314859041; \par \pard\li50\ri6\plain\f3\fs22\cf2\protect {\pict\wmetafile8\picw3104\pich827\picwgoal1759\pichgoal468 0100090000036B01000005001C0000000000050000000B0200000000050000000C023B03200C03 0000001E00030000001E00050000000C02D501E006050000000B020000000014000000FF060000 0600F602000024000100020000800080FF7FFF7F02000080FF7F0080FF7F0200040000002D0100 0004000000F001000008000000FA0200000000000000000000040000002D01000007000000FC02 0000000000000000040000002D0101001C000000FB0210FF000000000000900100000001070000 00417269616C00000004170AB350EC1200B8A4F177C1A4F1772030F377C51666AF040000002D01 020005000000020101000000050000000102FFFFFF00050000002E011800000005000000090200 00000004000000080100001C000000FB0210FF0000000000009001000000010700000054696D65 73204E657720526F6D616E00B8A4F177C1A4F1772030F377C51666AF040000002D0103000B0000 0026060F000C004D6174685479706500007B000500000009020000FF0007000000210501003101 3B016400070000002105010038013B01DC00070000002105010034013B01540107000000210501 0035013B01CC01070000002105010033013B014402070000002105010031013B01BC0207000000 2105010034013B013403070000002105010038013B01AC03070000002105010035013B01240407 0000002105010039013B019C04070000002105010030013B011405070000002105010034013B01 8C05070000002105010031013B01040608000000FA0200000000000000000000040000002D0104 0004000000F001000007000000FC020000FFFFFF000000040000002D01000004000000F0010100 1C000000FB021000070000000000BC02000000000102022253797374656D000085150A2150EC12 00B8A4F177C1A4F1772030F377C51666AF040000002D010100040000002701FFFF04000000F001 020004000000F0010300040000002701FFFF030000000000 }\plain\f3\fs22\cf2\protect \par \pard\li50\ri2\plain\f3\fs22\cf2\protect \par \pard\li300\ri5\fi-300{\*\pn\pnlvlblt\pnf1\pnindent300{\pntxtb\'b7}}\plain\f3\fs22\cf1 {\pntext\f1\'b7\tab} \par }