{VERSION 5 0 "IBM INTEL NT" "5.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Courier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 3 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Warning" 2 7 1 {CSTYLE "" -1 -1 "" 0 1 0 0 255 1 0 0 0 0 0 0 1 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT -1 57 "indexcalc.mws : computes d iscrete logs via index calculus" }}{PARA 0 "" 0 "" {TEXT -1 41 "writte n by seth hardy, shardy@tsumego.com" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "restart;\nwith(linalg):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "printlevel := 0;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#> %+printlevelG\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "rando mize():" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 148 "alpha := 5;\nbe ta := convert(\"361F2CAA21D41E7CA729C34AEDFBCC2B\",decimal,hex);\np := convert(\"968F4E0BB1990EE696DA1B3CA82DCFF7\",decimal,hex);\nn := p-1; " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&alphaG\"\"&" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%%betaG\"GbxmN,^%)[-gkmz-))y,%>(" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%\"pG\"H.Tv0feWF=HlhIHx!GG,?" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"H-Tv0feWF=HlhIHx!GG,?" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "basesize := ceil(log(p));\nnumequations := 2*bas esize;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%)basesizeG\"$y\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%-numequationsG\"$c$" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 46 "primebase := [seq(ithprime(i),i=1..basesize)]; " }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%*primebaseG7^v\"\"#\"\"$\"\"&\" \"(\"#6\"#8\"#<\"#>\"#B\"#H\"#J\"#P\"#T\"#V\"#Z\"#`\"#f\"#h\"#n\"#r\"# t\"#z\"#$)\"#*)\"#(*\"$,\"\"$.\"\"$2\"\"$4\"\"$8\"\"$F\"\"$J\"\"$P\"\" $R\"\"$\\\"\"$^\"\"$d\"\"$j\"\"$n\"\"$t\"\"$z\"\"$\"=\"$\">\"$$>\"$(> \"$*>\"$6#\"$B#\"$F#\"$H#\"$L#\"$R#\"$T#\"$^#\"$d#\"$j#\"$p#\"$r#\"$x# \"$\"G\"$$G\"$$H\"$2$\"$6$\"$8$\"$<$\"$J$\"$P$\"$Z$\"$\\$\"$`$\"$f$\"$ n$\"$t$\"$z$\"$$Q\"$*Q\"$(R\"$,%\"$4%\"$>%\"$@%\"$J%\"$L%\"$R%\"$V%\"$ \\%\"$d%\"$h%\"$j%\"$n%\"$z%\"$([\"$\"\\\"$*\\\"$.&\"$4&\"$@&\"$B&\"$T &\"$Z&\"$d&\"$j&\"$p&\"$r&\"$x&\"$(e\"$$f\"$*f\"$,'\"$2'\"$8'\"$<'\"$> '\"$J'\"$T'\"$V'\"$Z'\"$`'\"$f'\"$h'\"$t'\"$x'\"$$o\"$\"p\"$,(\"$4(\"$ >(\"$F(\"$L(\"$R(\"$V(\"$^(\"$d(\"$h(\"$p(\"$t(\"$(y\"$(z\"$4)\"$6)\"$ @)\"$B)\"$F)\"$H)\"$R)\"$`)\"$d)\"$f)\"$j)\"$x)\"$\"))\"$$))\"$())\"$2 *\"$6*\"$>*\"$H*\"$P*\"$T*\"$Z*\"$`*\"$n*\"$r*\"$x*\"$$)*\"$\"**\"$(** \"%45\"%85\"%>5\"%@5\"%J5\"%L5\"%R5\"%\\5\"%^5\"%h5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "getrandnum := rand(p):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 994 "numgood := 0:\nA := array(1..numequation s,1..basesize+1):\nbaselogs := vector(basesize,0):\n\nbasezero := true :\n\nwhile basezero do\n\n basezero := false:\n numgood := 0:\n\n w hile numgood < numequations do\n k := getrandnum();\n kexp := al pha&^k mod p; \n fac := ifactors(kexp);\n numfac := nops(op(2,fa c));\n bad := false;\n for i from 1 to numfac do\n if not o p(1,op(i,op(2,fac))) in primebase then\n bad := true;\n \+ break;\n fi;\n od; \n if not bad then \n v := vector (primebase[basesize],0);\n for i from 1 to numfac do\n v[o p(1,op(i,op(2,fac)))] := op(2,op(i,op(2,fac)));\n od;\n numg ood := numgood + 1; \n for i from 1 to basesize do A[numgood,i] : = v[ithprime(i)]; od;\n A[numgood,basesize+1] := k;\n fi;\n o d;\n\n B := map(modp,rref(A),n);\n baselogs := [seq(B[i,basesize+1], i=1..basesize)];\n\n for i from 1 to basesize do\n if baselogs[i] \+ = 0 then\n basezero := true;\n break;\n fi;\n od;\n\nod; \n\nprint(baselogs);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%)basezeroG%& falseG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(numgoodG\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"kG\"Hb'R!*f'zv\"f1Y0A[.^zmu=" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%kexpG\"GG'=R'p#[RC]+=4\"*4aGK:'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$facG7$\"\"\"7(7$\"\"#F)7$\"\"$F&7$\"+VX\" 3!\\F&7$\"2f]4)Q?BRQF&7$\"'ZK=F&7$\"'@([\"F&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%'numfacG\"\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$b adG%&falseG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$badG%%trueG" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"kG\"G[Cq_ZX(R93@ZOk&\\$HK(*)" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%%kexpG\"Hn88)HS&)4!H@4Vr(4yxE76" }} {PARA 7 "" 1 "" {TEXT -1 33 "Warning, computation interrupted\n" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 310 "while true do\n k := getra ndnum();\n kexp := alpha&^k mod p;\n z := beta*kexp;\n zfac := ifac tors(z);\n znumfac := nops(op(2,zfac));\n bad := false;\n for i fro m 1 to znumfac do\n if not op(1,op(i,op(2,zfac))) in primebase then \n bad := true;\n break;\n fi;\n od;\n if not bad then \+ break; fi; \nod;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 107 "bases := array(1..primebase[basesize]);\nfor i from 1 to basesize do bases[ ithprime(i)] := baselogs[i]; od;\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 94 "logbeta := add(bases[op(1,op(i,op(2,zfac)))] * op(2,o p(i,op(2,zfac))),i=1..znumfac) - k mod n;" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}} {MARK "3 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }