{VERSION 7 1 "Linux" "7.1" } {USTYLETAB {PSTYLE "Heading 4" -1 20 1 {CSTYLE "" -1 -1 "MS Serif" 1 12 0 0 0 1 1 2 2 2 2 2 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Ordered List 5" -1 200 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 144 2 0 2 2 -1 1 }{PSTYLE "Ordered List 1 " -1 201 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 } 1 1 0 0 3 3 2 0 2 0 2 2 -1 1 }{PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Courier" 1 12 0 0 255 1 2 2 2 2 2 1 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Bullet Item" -1 15 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 0 2 0 2 2 -1 1 }{PSTYLE "Left Justified Maple Output" -1 12 1 {CSTYLE "" -1 -1 "" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Help" -1 10 1 {CSTYLE "" -1 -1 "" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Author" -1 19 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }3 1 0 0 8 8 2 0 2 0 2 2 -1 1 }{PSTYLE "Diagnostic" -1 9 1 {CSTYLE "" -1 -1 "Courier" 1 12 40 120 40 1 2 2 2 2 2 1 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Heading 2" -1 4 1 {CSTYLE "" -1 -1 "MS Serif" 1 16 0 0 0 1 2 1 2 2 2 2 1 0 0 1 }1 1 0 0 8 2 2 0 2 0 2 2 -1 1 }{PSTYLE "Ordered List 3" -1 202 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 72 2 0 2 2 -1 1 }{PSTYLE "Maple Plot" -1 13 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Norm al" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 } 1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Dash Item" -1 16 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 0 2 0 2 2 -1 1 }{PSTYLE "Heading 3" -1 5 1 {CSTYLE "" -1 -1 "MS Serif" 1 14 0 0 0 1 1 1 2 2 2 2 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Orde red List 4" -1 203 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 108 2 0 2 2 -1 1 }{PSTYLE "Maple Output" -1 11 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Line Printed Output" -1 6 1 {CSTYLE "" -1 -1 "Courier" 1 12 0 0 255 1 2 2 2 2 2 1 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "List Item" -1 14 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 0 2 0 2 2 -1 1 }{PSTYLE "Wa rning" -1 7 1 {CSTYLE "" -1 -1 "Courier" 1 12 0 0 255 1 2 2 2 2 2 1 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Error" -1 8 1 {CSTYLE "" -1 -1 "Courier" 1 12 255 0 255 1 2 2 2 2 2 1 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Fixed Width" -1 17 1 {CSTYLE "" -1 -1 "" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "He ading 1" -1 3 1 {CSTYLE "" -1 -1 "MS Serif" 1 18 0 0 0 1 2 1 2 2 2 2 1 0 0 1 }1 1 0 0 8 4 2 0 2 0 2 2 -1 1 }{PSTYLE "Title" -1 18 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 0 0 1 }3 1 0 0 12 12 2 0 2 0 2 2 -1 1 }{PSTYLE "Ordered List 2" -1 204 1 {CSTYLE "" -1 -1 "Times " 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 36 2 0 2 2 -1 1 } {CSTYLE "Equation Label" -1 200 "Courier" 1 12 0 0 0 1 2 1 2 2 2 2 0 0 0 1 }{CSTYLE "Text" -1 201 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 } {CSTYLE "Page Number" -1 33 "Times" 1 10 0 0 0 1 2 2 2 2 2 2 0 0 0 1 } {CSTYLE "Maple Input" -1 0 "Courier" 1 12 255 0 0 1 2 1 2 2 1 2 0 0 0 1 }{CSTYLE "2D Output" -1 20 "Times" 1 12 0 0 255 1 2 2 2 2 2 1 0 0 0 1 }{CSTYLE "Dictionary Hyperlink" -1 45 "MS Serif" 1 12 147 0 15 1 2 2 1 2 2 2 0 0 0 1 }{CSTYLE "2D Input" -1 19 "Times" 1 12 0 0 0 1 2 2 2 2 1 2 0 0 0 1 }{CSTYLE "Maple Input Placeholder" -1 202 "Courier" 1 12 200 0 200 1 2 1 2 2 1 2 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }{CSTYLE "Hyperlink" -1 17 "MS Serif" 1 12 0 128 128 1 2 2 1 2 2 2 0 0 0 1 }{PSTYLE "" -1 205 1 {CSTYLE "" -1 -1 "Times" 1 12 255 0 0 1 2 1 2 2 1 2 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT 203 66 "Sz\303\241m\303\255t\303 \263g\303\251pes sz\303\241melm\303\251let" }}}{EXCHG {PARA 19 "" 0 "" {TEXT 204 18 "J\303\241rai Antal" }}}{EXCHG {PARA 19 "" 0 "" {TEXT 204 68 "Ezek a programok csak szeml\303\251ltet\303\251sre szolg\303\2 41lnak" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT 205 59 "1. A pr\303\255mek el oszl\303\241sa, szit\303\241l\303\241s" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT 205 63 "2. Egyszer\305\261 faktoriz\303\241l\303\241si m\303\263 dszerek" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 7 "2.1. Pr" }{TEXT 206 8 "\303\263" }{TEXT 206 6 "baoszt" }{TEXT 206 9 "\303 \241s" }{TEXT 206 1 "." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 34 "# This is a s imple factorization\n" }{MPLTEXT 1 0 35 "# procedure using trial divis ion.\n" }{MPLTEXT 1 0 37 "# The result is a sequence of pairs\n" } {MPLTEXT 1 0 37 "# [p,e] where the p's are the prime\n" }{MPLTEXT 1 0 42 "# factors and the e's are the exponents.\n" }{MPLTEXT 1 0 47 "# Th e factors are anyway in increasing order.\n" }{MPLTEXT 1 0 41 "# Only \+ primes <= P are tried, hence the\n" }{MPLTEXT 1 0 38 "# last \"factor \" may composite, if \n" }{MPLTEXT 1 0 27 "# it is greater then P^2;\n " }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 55 "trialdi v:=proc(n::posint,P::posint) local L,p,i,d,nn;\n" }{MPLTEXT 1 0 15 "L: =[]; nn:=n;\n" }{MPLTEXT 1 0 32 "if type(nn,even) and 2<=P then\n" } {MPLTEXT 1 0 53 " for i from 0 while type(nn,even) do nn:=nn/2; od;\n " }{MPLTEXT 1 0 15 " L:=[[2,i]];\n" }{MPLTEXT 1 0 5 "fi;\n" }{MPLTEXT 1 0 29 "if nn mod 3=0 and 3<=P then\n" }{MPLTEXT 1 0 50 " for i from 0 while nn mod 3=0 do nn:=nn/3; od;\n" }{MPLTEXT 1 0 21 " L:=[op(L), [3,i]];\n" }{MPLTEXT 1 0 5 "fi;\n" }{MPLTEXT 1 0 13 "d:=2; p:=5;\n" } {MPLTEXT 1 0 27 "while p<=P and nn>=p^2 do\n" }{MPLTEXT 1 0 22 " if n n mod p=0 then\n" }{MPLTEXT 1 0 52 " for i from 0 while nn mod p=0 \+ do nn:=nn/p; od;\n" }{MPLTEXT 1 0 23 " L:=[op(L),[p,i]];\n" } {MPLTEXT 1 0 7 " fi;\n" }{MPLTEXT 1 0 19 " p:=p+d; d:=6-d;\n" } {MPLTEXT 1 0 5 "od;\n" }{MPLTEXT 1 0 36 "if nn>1 then L:=[op(L),[nn,1] ] fi;\n" }{MPLTEXT 1 0 4 "L;\n" }{MPLTEXT 1 0 4 "end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6$'I\"nG6\"I'posintG%*protectedG'I\"PGF&F'6'I\"LGF& I\"pGF&I\"iGF&I\"dGF&I#nnGF&F&F&C+>F,7\">F0F%@$3-I%typeGF(6$F0I%evenGF (1\"\"#F*C$?(F.\"\"!\"\"\"F&F7>F0,$*&#F@FF,7#7$FF0,$*&#F@FNF@F0F@F@>F,7$-I#opGF(6#F ,7$FNF.>F/F<>F-\"\"&?(F&F@F@F&31F-F*1*$)F-FF0*&F0F@F-!\"\">F,7$FX7$F-F.>F-,&F-F@F/F@>F/,&\"\"'F@F/Fho@$ 2F@F0>F,7$FX7$F0F@F,F&F&F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "trialdiv(2^32+1,1000);" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$7$\"$T' \"\"\"7$\"( " 0 "" {MPLTEXT 1 0 3 "#\n" } {MPLTEXT 1 0 38 "# This is a simple primality testing\n" }{MPLTEXT 1 0 35 "# procedure using trial division.\n" }{MPLTEXT 1 0 49 "# The res ult is true if n is prime, else false.\n" }{MPLTEXT 1 0 3 "#\n" } {MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 47 "trialprime:=proc(n::posint) loca l L,p,i,d,nn;\n" }{MPLTEXT 1 0 31 "if n=1 then RETURN(false) fi;\n" } {MPLTEXT 1 0 44 "if n=2 or n=3 or n=5 then RETURN(true) fi;\n" } {MPLTEXT 1 0 40 "if type(n,even) then RETURN(false) fi;\n" }{MPLTEXT 1 0 37 "if n mod 3=0 then RETURN(false) fi;\n" }{MPLTEXT 1 0 13 "d:=2; p:=5;\n" }{MPLTEXT 1 0 17 "while n>=p^2 do\n" }{MPLTEXT 1 0 39 " if \+ n mod p=0 then RETURN(false) fi;\n" }{MPLTEXT 1 0 19 " p:=p+d; d:=6-d ;\n" }{MPLTEXT 1 0 14 "od; true; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#'I\"nG6\"I'posintG%*protectedG6'I\"LGF&I\"pGF&I\"iGF&I\"dGF&I#nnG F&F&F&C*@$/F%\"\"\"-I'RETURNGF(6#I&falseGF(@$55/F%\"\"#/F%\"\"$/F%\"\" &-F46#I%trueGF(@$-I%typeGF(6$F%I%evenGF(F3@$/-I$modGF&6$F%F=\"\"!F3>F- F;>F+F??(F&F2F2F&1*$)F+F;F2F%C%@$/-FK6$F%F+FMF3>F+,&F+F2F-F2>F-,&\"\"' F2F-!\"\"FBF&F&F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "trialp rime(2^32+1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "I&falseG%*protectedG" } }}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 13 "2.2. Feladat." }}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 13 "2.3. Feladat." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "interface(verbose proc=2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "print(ifactor);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"nG6\"6%I$solGF%I\"rGF%I#t1GF%6%I)rememberGF%I'systemG%*prot ectedGIaoCopyright~(c)~1991~by~the~University~of~Waterloo.~All~rights~ reserved.GF%E\\s*\"-g$H*4x)**4)-I!GF%6#\"\"#\"\"%\"\"\"-F46#\"\"$F8-F4 6#\"\"&F8-F46#\"\"(F8-F46#\"#6F8-F46#\"#F8-F46#\" $n\"F8\"-SEmBx)**4F2F8F9F8FF'F8>F (F$2F$FbuC$>F'!\"\">F(,$F$FiuOFbu-Fct6$F$.I)fractionGF-O*&-%)procnameG 6$-I#opGF-6$F8F$&Fft6#;F6FiuF8-Fdv6$-Fgv6$F6F$FivFiu-Fct6$F$<&.I\"*GF- .I%listGF-.I$setGF-.I)relationGF-O-I$mapGF-6%FdvF$Fiv3-Fct6$F$I\"^GF-- Fct6$F^wF^uO)FcvF^w-Fct6$F$-F46#F^uOFcvYQ2invalid~argumentsF%@$-I)assi gnedGF-6#&I7ifactor/from_signatureGF%6#F(OFby>F)-I%igcdGF-6$F(\"'?2s?( F%F8F8F%0F)F8C%>F'*&F'F8-I1ifactor/ifact235GF%6#F)F8>F(-I%iquoGF-6$F(F )>F)-Fhy6$F)F(>F)-Fhy6$F(\"igmL#4(*G]KKT_/&o:-6-\\ULnO63K//a2+Jg1(yv%) )=%>78\">_=)RBQ#>VWyw'G*R%G\\?$f7!e@ZzI(*yye56c\"y)**o*)QLhqw-?=(zuT%e <6)fZ@Q*[2)3#>wd'*\\:G(*)z=]^VV.h9MkueL(z![$)**Hq1x_w')Rd#QeVva%>VJ\") )ez>!*He%\\xPDRmf-60&3OlWa]rHz(zX$[VqF@7Hs,A!zAnr6'>C%\\$fw>r,cG\"31+7 sAdQ@A(zC>XzNl(*4)\\0aFc@**)y;u2(R&)H\\..*H7\"yV-VoEZ>IAzQ%H3>#=%y%))* Q?>l?')f!pq1Vkpj(4R=cVxQ,'o1aK,npXBR,W[tUA)H'4-FhUPX3y&*3(>b')GHWsiV[_ .pt5=bqyi!=TRbUc#=@W,P9^Ha;\"?(F%F8F8F%F\\zC%>F'*&F'F8-I1ifactor/ifact 1stGF%FbzF8FczFgz@%0F(F8C$@%/F\\tF8@%3/I2_Env_ifactor_easyGF%I%trueGF- 2\"#I-I'lengthGF-FdyC$>I/ifactor/bottomGF%I-ifactor/easyGF%>F)-I1ifact or/ifact0thGF%FdyC$>Fd\\lI.ifactor/mixedGF%Ff\\lC$>Fd\\l-I$catGF-6$I)i factor/GF%Fet>F)-Fh\\l6$F(&Fft6#;F;F\\t@%0F)I%FAILGF-*&F'F8F)F8Fj]lF'F %6#Fd\\lF%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "print(`ifacto r/ifact235`);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"nG6\"6#I\"qGF%6% I)rememberGF%I'systemG%*protectedGIaoCopyright~(c)~1991~by~the~Univers ity~of~Waterloo.~All~rights~reserved.GF%E\\sB\"\"\"F.\"\"#-I!GF%6#F/\" \"$-F16#F3\"$_#*()F0F/F.)F4F/F.-F16#\"\"(F.\"\"&-F16#F=\"%SE**)F0\"\"% F.F4F.F>F.-F16#\"#6F.FC*$F8F.\"#5*&F0F.F>F.\"\")*$)F0F3F.\"\"**$F9F.\" #:*&F4F.F>F.\"#!**(F0F.F9F.F>F.\"%?z**FBF.F9F.F>F.FDF.\"$S#*(FBF.F4F.F >F.\"'?2s*.FBF.F9F.F>F.F:F.FDF.-F16#\"#8F.\"#?*&F8F.F>F.\"&?V$*,FBF.F4 F.F>F.FDF.FYF.\"#=*&F0F.F9F.\"#I*(F0F.F4F.F>F.\"$!=*(F8F.F9F.F>F.\"%!o %**FLF.F9F.F>F.FYF.\"%S]**FBF.F9F.F>F.F:F.\"#S*&FLF.F>F.\"$?(*(FBF.F9F .F>F.\"#X*&F9F.F>F.\"$?\"*(FLF.F4F.F>F.\"#O*&F8F.F9F.\"#j*&F9F.F:F.\"$ g$*(FLF.F9F.F>F.\"#g*(F8F.F4F.F>F.\"&Sa&*,FBF.F9F.F>F.F:F.FDF.\"%!o\"* *FBF.F4F.F>F.F:F.\"&![=*,FBF.F4F.F>F.F:F.FDF.@//F$F.F./-I%iremGF+6%F$F en.F'\"\"!*&-I1ifactor/ifact235GI(_syslibGF%F&F.FYF./-F^q6%F$FFF`qFaq* &FcqF.FDF./-F^q6%F$FF%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "print(`ifactor/ifact0th`);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f *6#I\"nG6\"6$I$solGF%I\"pGF%6#IaoCopyright~(c)~1991~by~the~University~ of~Waterloo.~All~rights~reserved.GF%F%C,@$2F$\"(\"o?HO-I!GF%F#@$-I(isp rimeGF%F#F/>F'-I.ifactor/powerGF%6$F$.F(@$0F'I%FAILG%*protectedGO)-I1i factor/ifact0thGI(_syslibGF%6#F'F(>F'-I/ifactor/pollp1GF%6$F$\"&.I\"@$ /F'I*_tryagainGF%>F'-FF6$F$\"&/I\"@$FJ>F'F<@$/F'F<>F'-I1ifactor/pp1000 00GF%F#@$FSC$>F'-I/ifactor/bottomGF%6#%%argsG@$4-I%typeGF=6$F'.I(integ erGF=OF'*&-FA6$*&F$\"\"\"F'!\"\"&Fgn6#;\"\"#%&nargsGFdo-FA6$F'FfoFdoF% F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "print(`ifactor/ifac t1st`);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"nG6\"6'I\"iGF%I#igGF%I \"rGF%I$solGF%I#t1GF%6%I)rememberGF%I'systemG%*protectedGIaoCopyright~ (c)~1991~by~the~University~of~Waterloo.~All~rights~reserved.GF%E\\s)\" '\"4u#*(-I!GF%6#\"#<\"\"\"-F56#\"#BF8-F56#\"$,(F8\")xj!e(*,-F56#\"#HF8 -F56#\"#JF8-F56#\"#PF8-F56#\"#VF8-F56#\"#`F8\")F)z(G**F4F8-F56#\"#TF8- F56#\"$d\"F8-F56#\"$j#F8\".@gQx![S*0FRF8-F56#\"#fF8-F56#\"#hF8-F56#\"# nF8-F56#\"#rF8-F56#\"#tF8-F56#\"#zF8F7F4\"&TR&*(F4F8-F56#\"#>F8-F56#\" $n\"F8\")2vW`**F4F8-F56#\"#ZF8-F56#\"$^\"F8-F56#\"$V%F8\"'>TP*(F4F8Fgn F8-F56#\"$t$F8C&>F*F8>F)F$?(F'F8F8\"\"(0F)F8C$>F(-I%igcdGF/6$F)&7)\"$B $\"'\\]w\".*=Sw'*e5\"=f;keB!QSk)[oMo\"*\"jn*)Q)fV\"f7sR%>OC%Qc5Ha=4+Wo $Q&y @J463'eRLU2C3>ZQ7W@n9:A\"))GK!>*))4Fz\"jfl\\m=,#HR1()**zpV7B5YFxB^'fx^ wm+l#)=k8a:?(>ow)[NTVda@\\TmBev!>nUv%e'*)f'*[pCwUbW1A%pu#fd4NQm:'fh3xp wAo4'Q&*Q,qClPM7O[d+w/IbSU?hph,9UAc$=>WcF`M=;c$\\D&RT,aa%Q$Qnk.k&y\"*R \"HzZ#H/kVngfrpUNk)>$zl>V^_W6cdEqT)33N;\"o)3x&Hj'pUu_aA9:`c;]$o'pzI&GG \"4N:U/w]M;77z\"6#F'@$0F(F8C%>F)-I%iquoGF/6$F)F(?(F%F8F8F%1&7)F^r\"$n' \"%j<\"%$=&\"&62#\"&>H)\"'`[WFerF(C%>F+-I2ifactor/wheelfactGF%6$F(&7)F 7F;FTFbo\"$R\"\"$$G\"$h'Fer>F**&F*F8-F56#F+F8>F(-F[s6$F(F+>F**&F*F8-F5 6#F(F8OF*F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "print(`i factor/wheelfact`);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6$I\"nG6\"I\"sG F%6%I\"iGF%I#iiGF%I#t1GF%6#IaoCopyright~(c)~1991~by~the~University~of~ Waterloo.~All~rights~reserved.GF%F%?(F(,&*&\"#I\"\"\"-I%iquoG%*protect edG6$F&F0F1F1\"#:F1F0F%I%trueGF4C$>F**$)F(\"\"#F1@$0-I%igcdGF46$F$**,& F*F1\"\"%!\"\"F1,&F*F1\"#;FEF1,&F*F1\"#kFEF1,&F*F1\"$'>FEF1F1?(F),&F(F 1\"#9FEF " 0 "" {MPLTEXT 1 0 24 "print(`ifactor/pollp1`);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6$I\"nG6\"I%seedGF%6)I'primesGF%I/factorizationsGF%I\"w GF%I\"iGF%I#t1GF%I%pairGF%I\"dGF%6#IaoCopyright~(c)~1990~by~the~Univer sity~of~Waterloo.~All~rights~reserved.GF%F%C'>F(7V\"$7&\"+D1S,F\",(*3D p`\"\"/6y%eA>?#\".x8FEAJ$\"-8lv!Qt&\".P>V:f*)*\".P\\9K5!**\"/807M$en# \"0fit_cM@#\"0rjGNj*=N\"0P2lTF`-'\"0pNY8e!fq\"1rJad-'o9\"\"1>w;QM#z>\" \"1`3NAG=,T\"2H!*[p@j$4=\"2*>\\BLTty:\"28T$o`)pT0$\"2xFV5b'GFK\"2*G[fQ BK>!*\"2$f>Bjz#f[*\"3H%[H%p&y&4A\"3$*\\Gf*znU<#\"3@2>\"=A&=QN\"3*[%)GY X**R>%\"3dMJn!*=Wsd\"3B7w-)[kcw&\"38ej;$R/,N'\"4H1$Rd1'3K;\"\"4`JrgKaF XF\"\"3xY'GW$[,U'*\"4\")>%3ca!\\&*=\"\"4LNqO#H5mI<\"4hP!3'o*f_CB\"4Zl( *=\\2z$\\<\"4hZZ'=)4=$zB\"4j=-Ni+5j!R\"4LkaoH$p.+W\"4T=HP@(yN'[$\"428J ID&3b^S\"48Hb8>?CH1(\"4d'Gn*yQ/i%**\"4@S#3!G$*>/!)*\"5J:KQJX;k,9\"5t-* [jcqa^%=\"5HN!oH\">R3x?\"5*)e[!)Q(yBiK#\"5p(G%y_YAHGG\"5V9q;)H+UzP#\"5 .+A/+OFk+H\"8\\#HkoRH87%HK'>F)7V7#7$\"\"#\"\"*7&7$\"\"$\"\"'7$\"\"&\" \"%7$\"\"(Ffo7$\"#6Ffo7'7$F`p\"\"\"7$FbpFep7$\"#8Ffo7$\"#JFfo7$\"%H7Fe p7(7$\"#Ffo7$\"#BFfo7$\"#PFep7$\"#TFep7$\"$j#Fep7(7$\"#HFfo7 $\"#VFep7$\"#ZFep7$\"#`Fep7$\"#$)Fep7$\"$V%Fep7(7$\"#fFep7$\"#hFep7$\" #nFep7$\"#rFep7$\"$2\"Fep7$\"$8$Fep7(7$\"#tFep7$\"#zFep7$\"#*)Fep7$\"# (*Fep7$\"$8\"Fep7$\"%fFep7$\"$\\$Fep7(7$\"$J\"Fep7$\"$P\"Fep7$\"$R\"Fep7$\"$\\\"Fep 7$\"$$>Fep7$\"$t$Fep7(7$\"$^\"Fep7$\"$d\"Fep7$\"$j\"Fep7$\"$n\"Fep7$\" $F#Fep7$\"%6:Fep7(7$\"$t\"Fep7$\"$z\"Fep7$\"$\"=Fep7$\"$\">Fep7$\"$d#F ep7$\"%z7Fep7(7$\"$*>Fep7$\"$6#Fep7$\"$B#Fep7$\"$H#Fep7$\"$([Fep7$\"$x &Fep7(7$\"$L#Fep7$\"$R#Fep7$\"$T#Fep7$\"$^#Fep7$\"$n$Fep7$\"$r&Fep7(7$ \"$p#Fep7$\"$r#Fep7$\"$x#Fep7$\"$\"GFep7$\"$f$Fep7$\"$j&Fep7(7$\"$$GFe p7$\"$$HFep7$\"$2$Fep7$\"$6$Fep7$\"$P$Fep7$\"$\\%Fep7(7$\"$<$Fep7$\"$J $Fep7$\"$Z$Fep7$\"$z$Fep7$\"$R%Fep7$\"$x'Fep7(7$\"$`$Fep7$\"$$QFep7$\" $*QFep7$\"$(RFep7$\"$p&Fep7$\"%B:Fep7(7$\"$,%Fep7$\"$4%Fep7$\"$>%Fep7$ \"$@%Fep7$\"$*fFep7$\"$6*Fep7(7$\"$J%Fep7$\"$L%Fep7$\"$d%Fep7$\"$h%Fep 7$\"$<'Fep7$\"%f7Fep7(7$\"$j%Fep7$\"$n%Fep7$\"$z%Fep7$\"$\"\\Fep7$\"$t (Fep7$\"$@)Fep7(7$\"$*\\Fep7$\"$.&Fep7$\"$4&Fep7$\"$@&Fep7$\"$,(Fep7$ \"%L>Fep7(7$\"$B&Fep7$\"$T&Fep7$\"$Z&Fep7$\"$d&Fep7$\"$\"))Fep7$\"%\\7 Fep7(7$\"$(eFep7$\"$$fFep7$\"$,'Fep7$\"$2'Fep7$\"$H*Fep7$\"%t=Fep7(7$ \"$8'Fep7$\"$>'Fep7$\"$J'Fep7$\"$T'Fep7$\"$r*Fep7$\"%f9Fep7(7$\"$V'Fep 7$\"$Z'Fep7$\"$`'Fep7$\"$f'Fep7$\"%85Fep7$\"%^>Fep7(7$\"$h'Fep7$\"$t'F ep7$\"$$oFep7$\"$\"pFep7$\"%\"4\"Fep7$\"%J=Fep7(7$\"$4(Fep7$\"$>(Fep7$ \"$F(Fep7$\"$L(Fep7$\"%j5Fep7$\"%**>Fep7(7$\"$R(Fep7$\"$V(Fep7$\"$^(Fe p7$\"$d(Fep7$\"$$)*Fep7$\"%z=Fep7(7$\"$h(Fep7$\"$p(Fep7$\"$(yFep7$\"$( zFep7$\"$n*Fep7$\"%*y\"Fep7(7$\"$4)Fep7$\"$6)Fep7$\"$B)Fep7$\"$F)Fep7$ \"%28Fep7$\"%$*>Fep7(7$\"$H)Fep7$\"$R)Fep7$\"$`)Fep7$\"$d)Fep7$\"%F8Fe p7$\"%*)=Fep7(7$\"$f)Fep7$\"$j)Fep7$\"$x)Fep7$\"$$))Fep7$\"%\"H\"Fep7$ \"%,8Fep7(7$\"$())Fep7$\"$2*Fep7$\"$>*Fep7$\"$P*Fep7$\"%$4\"Fep7$\"%r: Fep7(7$\"$T*Fep7$\"$Z*Fep7$\"$`*Fep7$\"$x*Fep7$\"%@8Fep7$\"%z:Fep7(7$ \"$\"**Fep7$\"$(**Fep7$\"%45Fep7$\"%>5Fep7$\"%B7Fep7$\"%r=Fep7(7$\"%@5 Fep7$\"%J5Fep7$\"%L5Fep7$\"%\\5Fep7$\"%<6Fep7$\"%t8Fep7(7$\"%R5Fep7$\" %^5Fep7$\"%h5Fep7$\"%p5Fep7$\"%P7Fep7$\"%`:Fep7(7$\"%(3\"Fep7$\"%(4\"F ep7$\"%.6Fep7$\"%B6Fep7$\"%49Fep7$\"%x=Fep7(7$\"%46Fep7$\"%H6Fep7$\"%^ 6Fep7$\"%j6Fep7$\"%\"Q\"Fep7$\"%,>Fep7(7$\"%`6Fep7$\"%r6Fep7$\"%\"=\"F ep7$\"%(=\"Fep7$\"%*G\"Fep7$\"%H9Fep7(7$\"%$>\"Fep7$\"%,7Fep7$\"%87Fep 7$\"%<7Fep7$\"%$G\"Fep7$\"%$\\\"Fep7(7$\"%J7Fep7$\"%x7Fep7$\"%(H\"Fep7 $\"%.8Fep7$\"%V:Fep7$\"%B8Fep7$\"%h8Fep7$\"%n8Fep7$\"%L9Fe p7$\"%>;Fep7$\"%ZFe p7$\"%Z=Fep7(7$\"%*[\"Fep7$\"%J:Fep7$\"%\\:Fep7$\"%n;Fep7$\"%z>Fep7$\" %$y\"Fep7(7$\"%f:Fep7$\"%n:Fep7$\"%$e\"Fep7$\"%$p\"Fep7$\"%B=Fep7$\"% \\>Fep7(7$\"%2;Fep7$\"%4;Fep7$\"%8;Fep7$\"%(*>Fep7$\"%()>Fep7$\"%4Fep7)7$\"%*p\"F ep7$\"%2>Fep7$\"%LFep7$\"%6=Fep7$\"%TF*F&?(F +FepFep-I%nopsG%*protectedG6#F(I%trueGF`imC$>F,-I%modpGF`im6$-I&powerG F%6$F*&F(6#F+F$@%0-I%igcdGF`im6$,&F,FepFep!\"\"F$FepC&@$0F,FepOF_jm>F. &F)F\\jm?&F-F.Fbim?(F%FepFep&F-6#FfoFbimC$>F*-Ffim6$-Fiim6$F*&F-6#FepF $@&/F*Fep@$2FepF+O-%)procnameG6$F$-Ffim6$-Fiim6$F&Fd[nF$0-F`jm6$,&F*Fe pFepFcjmF$FepOFc\\nOI*_tryagainGF%>F*F,I%FAILGF`imF%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "print(`ifactor/pp100000`);" }} {PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"nG6\"6$I\"iGF%I\"tGF%6#IaoCopyrig ht~(c)~1990~by~the~University~of~Waterloo.~All~rights~reserved.GF%F%C$ ?(F'\"%+S\"%+g\"&+S*I%trueG%*protectedGC$>F(-I%igcdGF16$(I&_prprGF%F'F $@$0F(\"\"\"@%0F(F$-I'RETURNGF16#F(-F?6#-I2ifactor/wheelfactGI(_syslib GF%6$F$,&F'F;F;F;I%FAILGF1F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "print(`ifactor/easy`);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I \"nG6\"F%6#IaoCopyright~(c)~1990~by~the~University~of~Waterloo.~All~ri ghts~reserved.GF%F%-&I0tools/genglobalGF%6#\"\"\"6#-I$catG%*protectedG 6&I!GF%.I#_cGF%-I'lengthGF0F#.I\"_GF%F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "print(`ifactor/ifact235`);" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"nG6\"6#I\"qGF%6%I)rememberGF%I'systemG%*protectedG IaoCopyright~(c)~1991~by~the~University~of~Waterloo.~All~rights~reserv ed.GF%E\\sB\"\"\"F.\"\"#-I!GF%6#F/\"\"$-F16#F3\"$_#*()F0F/F.)F4F/F.-F1 6#\"\"(F.\"\"&-F16#F=\"%SE**)F0\"\"%F.F4F.F>F.-F16#\"#6F.FC*$F8F.\"#5* &F0F.F>F.\"\")*$)F0F3F.\"\"**$F9F.\"#:*&F4F.F>F.\"#!**(F0F.F9F.F>F.\"% ?z**FBF.F9F.F>F.FDF.\"$S#*(FBF.F4F.F>F.\"'?2s*.FBF.F9F.F>F.F:F.FDF.-F1 6#\"#8F.\"#?*&F8F.F>F.\"&?V$*,FBF.F4F.F>F.FDF.FYF.\"#=*&F0F.F9F.\"#I*( F0F.F4F.F>F.\"$!=*(F8F.F9F.F>F.\"%!o%**FLF.F9F.F>F.FYF.\"%S]**FBF.F9F. F>F.F:F.\"#S*&FLF.F>F.\"$?(*(FBF.F9F.F>F.\"#X*&F9F.F>F.\"$?\"*(FLF.F4F .F>F.\"#O*&F8F.F9F.\"#j*&F9F.F:F.\"$g$*(FLF.F9F.F>F.\"#g*(F8F.F4F.F>F. \"&Sa&*,FBF.F9F.F>F.F:F.FDF.\"%!o\"**FBF.F4F.F>F.F:F.\"&![=*,FBF.F4F.F >F.F:F.FDF.@//F$F.F./-I%iremGF+6%F$Fen.F'\"\"!*&-I1ifactor/ifact235GI( _syslibGF%F&F.FYF./-F^q6%F$FFF`qFaq*&FcqF.FDF./-F^q6%F$FF%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "interface(echo=3);" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "read(\"../../../tmp/ifactor\");" }}{PARA 6 "" 1 "" {TEXT 207 1 "#" }}{PARA 6 "" 1 "" {TEXT 207 54 "# This is a commented \+ version of the Maple procedure\n" }{TEXT 207 40 "# ifactor for analysi s of the methods.\n" }{TEXT 207 3 "#\n" }{TEXT 207 56 "# The input par ameter n in general a positive integer.\n" }{TEXT 207 3 "#\n" }{TEXT 207 51 "# After a parameter cheking other cases: negative\n" }{TEXT 207 48 "# integer, rational numbers, etc. are treated.\n" }{TEXT 207 3 "#\n" }{TEXT 207 55 "# The first step is remove factors 2, 3, 5,7, 1 1, 13.\n" }{TEXT 207 55 "# gcd(n,2^4*3^2*5*7*11*13) calculated until b ecame 1.\n" }{TEXT 207 57 "# If it is greater then 1, then this gcd is factored by\n" }{TEXT 207 39 "# the small routine ifactor/ifact235.\n " }{TEXT 207 3 "#\n" }{TEXT 207 65 "# The second step is remove somewh at larger prime factors below\n" }{TEXT 207 68 "# from 17 to 1699. Thi s also happens with the gcd trick. Until the\n" }{TEXT 207 65 "# gcd i s larger then 1, the routine ifactor/ifact1st find these\n" }{TEXT 207 25 "# factors from the gcd.\n" }{TEXT 207 3 "#\n" }{TEXT 207 62 "# If the remainder still greater then 1, then the procedure \n" }{TEXT 207 66 "# corresponding to the second parameter is loaded until the na me\n" }{TEXT 207 62 "# `ifactor/bottom` and the procedure ifactor/ifac t0th called\n" }{TEXT 207 47 "# with passing thierd and further parame ters.\n" }{TEXT 207 40 "# This procedure use `ifactor/bottom`.\n" } {TEXT 207 3 "#\n" }{TEXT 207 65 "# If no second parameter is passed, t hen the `ifactor/morrbril`\n" }{TEXT 207 63 "# procedure loaded and th e procedure ifactor/ifact0th called.\n" }{TEXT 207 3 "#\n" }{TEXT 207 4 "> \n" }{TEXT 207 19 "> ifactor=proc(n)\n" }{TEXT 207 16 "> local so l,r;\n" }{TEXT 207 28 "> global `ifactor/bottom`;\n" }{TEXT 207 72 "> \+ options remember,system,`Copyright 1993 by Waterloo Maple Software`;\n " }{TEXT 207 65 "> if nargs < 1 or 1 < nargs and not type(args[2], name) then\n" }{TEXT 207 38 "> ERROR(`invalid arguments`)\n" } {TEXT 207 11 "> fi;\n" }{TEXT 207 31 "> if type(n,integer) the n\n" }{TEXT 207 42 "> if 0 < n then sol := 1; r := n\n" }{TEXT 207 46 "> elif n < 0 then sol := -1; r := -n\n" }{TEXT 207 26 "> else RETURN(0)\n" }{TEXT 207 14 "> fi\n" }{TEXT 207 76 "> elif type(n,fraction) then RETURN(ifactor(op(1,n))/ifact or(op(2,n)))\n" }{TEXT 207 74 "> elif type(n,\{`*`,set,list,relati on\}) then RETURN(map(ifactor,n))\n" }{TEXT 207 55 "> elif type(n, `^`) and type(op(2,n),integer) then\n" }{TEXT 207 44 "> RETURN (ifactor(op(1,n))^op(2,n))\n" }{TEXT 207 62 "> elif type(n,``(inte ger)) then RETURN(ifactor(op(1,n)))\n" }{TEXT 207 39 "> else ERROR (`invalid arguments`)\n" }{TEXT 207 11 "> fi;\n" }{TEXT 207 23 "> \+ igcd(r,720720);\n" }{TEXT 207 23 "> while % <> 1 do\n" }{TEXT 207 74 "> sol := sol*`ifactor/ifact235`(%); r := iquo(r,%%); i gcd(%%%,r)\n" }{TEXT 207 11 "> od;\n" }{TEXT 207 735 "> igcd(r ,116542951143701442118256425539411806278705518107369035248436272442928 8655197089578084537426127020962982242734844013923456967013254066860138 7743561839097636964430670690598620651920389884784182190829438792230194 7266843024378112299030349298539707741678899215627540549809976535794519 2479722213857227212000608128560171197659349424196117167227902201722912 2127704348345797792971505444653608505110259663925377749458299019795888 1314319454754358382573986765277067029998348079733587464341461034343515 0187989728154996577619208807489382147598111758441747971820027670613338 8968998781561110587878973079472158012593204928439928676784443192382339 8185219113121941888475787066031000754040432081136673342490211021568504 5241323250289709233);\n" }{TEXT 207 23 "> while % <> 1 do\n" } {TEXT 207 74 "> sol := sol*`ifactor/ifact1st`(%); r := iquo(r, %%); igcd(%%%,r)\n" }{TEXT 207 11 "> od;\n" }{TEXT 207 22 "> i f r <> 1 then\n" }{TEXT 207 29 "> if nargs = 1 then\n" }{TEXT 207 66 "> `ifactor/bottom` := readlib('`ifactor/morrbril`' );\n" }{TEXT 207 37 "> `ifactor/ifact0th`(r)\n" }{TEXT 207 16 "> else\n" }{TEXT 207 64 "> `ifactor/bottom ` := readlib(`ifactor/`.args[2]);\n" }{TEXT 207 54 "> `ifa ctor/ifact0th`(r,args[3 .. nargs])\n" }{TEXT 207 15 "> fi;\n" }{TEXT 207 48 "> if % <> FAIL then sol*% else FAIL fi\n" } {TEXT 207 16 "> else sol\n" }{TEXT 207 10 "> fi\n" }{TEXT 207 6 "> end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "/I(ifactorG6$%*protectedGI( _syslibG6\"f*6#I\"nGF'6$I$solGF'I\"rGF'6%I)rememberGF'I'systemGF%IJCop yright~1993~by~Waterloo~Maple~SoftwareGF'F'C)@$52%&nargsG\"\"\"32F7F64 -I%typeGF%6$&%%argsG6#\"\"#I%nameGF%-I&ERRORGF%6#I2invalid~argumentsGF '@--F<6$F*I(integerGF%@'2\"\"!F*C$>F,F7>F-F*2F*FMC$>F,!\"\">F-,$F*FT-I 'RETURNGF%6#FM-F<6$F*I)fractionGF%-FX6#*&-F#6#-I#opGF%6$F7F*F7-F#6#-F] o6$FAF*FT-F<6$F*<&I\"*GF%I$setGF%I)relationGF%I%listGF%-FX6#-I$mapGF%6 $F#F*3-F<6$F*I\"^GF%-F<6$FaoFJ-FX6#)FjnFao-F<6$F*-I!GF'6#FJ-FX6#FjnFC- I%igcdGF%6$F-\"'?2s?(F'F7F7F'0I\"%GF'F7C%>F,*&F,F7-I1ifactor/ifact235G F&6#FeqF7>F--I%iquoGF%6$F-I#%%GF'-F`q6$I$%%%GF'F--F`q6$F-\"igmL#4(*G]K KT_/&o:-6-\\ULnO63K//a2+Jg1(yv%))=%>78\">_=)RBQ#>VWyw'G*R%G\\?$f7!e@Zz I(*yye56c\"y)**o*)QLhqw-?=(zuT%e<6)fZ@Q*[2)3#>wd'*\\:G(*)z=]^VV.h9Mkue L(z![$)**Hq1x_w')Rd#QeVva%>VJ\"))ez>!*He%\\xPDRmf-60&3OlWa]rHz(zX$[VqF @7Hs,A!zAnr6'>C%\\$fw>r,cG\"31+7sAdQ@A(zC>XzNl(*4)\\0aFc@**)y;u2(R&)H \\..*H7\"yV-VoEZ>IAzQ%H3>#=%y%))*Q?>l?')f!pq1Vkpj(4R=cVxQ,'o1aK,npXBR, W[tUA)H'4-FhUPX3y&*3(>b')GHWsiV[_.pt5=bqyi!=TRbUc#=@W,P9^Ha;\"?(F'F7F7 F'FdqC%>F,*&F,F7-I1ifactor/ifact1stGF&F[rF7F\\rFar@%0F-F7C$@%/F6F7C$>I /ifactor/bottomGF'-I(readlibGF%6#.I1ifactor/morrbrilGF'-I1ifactor/ifac t0thGF&6#F-C$>Fds-Ffs6#-I\".GF'6$I)ifactor/GF'F>-F[t6$F-&F?6#;\"\"$F6@ %0FeqI%FAILGF%*&F,F7FeqF7F]uF,F'6#FdsF'" }}{PARA 6 "" 1 "" {TEXT 207 4 "> \n" }{TEXT 207 4 "> \n" }{TEXT 207 3 "#\n" }{TEXT 207 43 "# This \+ small routine find the factors of \n" }{TEXT 207 41 "# a positive inte ger known to have the \n" }{TEXT 207 44 "# gcd of 2^4*3^2*5*7*11*13 an d the number \n" }{TEXT 207 47 "# to factor. The factorization is give n back.\n" }{TEXT 207 3 "#\n" }{TEXT 207 4 "> \n" }{TEXT 207 28 "> ifa ctor/ifact235=proc(n)\n" }{TEXT 207 12 "> local q;\n" }{TEXT 207 72 "> options remember,system,`Copyright 1993 by Waterloo Maple Software`; \n" }{TEXT 207 23 "> if n = 1 then 1\n" }{TEXT 207 65 "> elif \+ irem(n,13,'q') = 0 then `ifactor/ifact235`(q)*``(13)\n" }{TEXT 207 65 "> elif irem(n,11,'q') = 0 then `ifactor/ifact235`(q)*``(11)\n" } {TEXT 207 63 "> elif irem(n,7,'q') = 0 then `ifactor/ifact235`(q)* ``(7)\n" }{TEXT 207 63 "> elif irem(n,2,'q') = 0 then ``(2)*`ifact or/ifact235`(q)\n" }{TEXT 207 63 "> elif irem(n,3,'q') = 0 then `` (3)*`ifactor/ifact235`(q)\n" }{TEXT 207 18 "> else ``(5)\n" }{TEXT 207 10 "> fi\n" }{TEXT 207 6 "> end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "/*&I(ifactorG6$%*protectedGI(_syslibG6\"\"\"\"I)ifact235G F(!\"\"f*6#I\"nGF(6#I\"qGF(6%I)rememberGF(I'systemGF&IJCopyright~1993~ by~Waterloo~Maple~SoftwareGF(F(@//F.F)F)/-I%iremGF&6%F.\"#8.F0\"\"!*&- I1ifactor/ifact235GF'F/F)-I!GF(6#F;F)/-F96%F.\"#6F \n" }{TEXT 207 4 "> \n" }{TEXT 207 3 "#\n" }{TEXT 207 54 "# T his routine find the factors from 17 to 1699. The\n" }{TEXT 207 55 "# \+ input is a positive integer containing only factors\n" }{TEXT 207 24 " # between 17 and 1699.\n" }{TEXT 207 3 "#\n" }{TEXT 207 47 "# The rout ine divides first the factors into \n" }{TEXT 207 42 "# smaller groups 17--19, 23--37, 41--67,\n" }{TEXT 207 62 "# 71--137, 139-281, 283--65 9, 661--1699 using the gcd trick.\n" }{TEXT 207 57 "# Then, depending \+ on the gcd obtained, a search routine\n" }{TEXT 207 54 "# ifactor/whee lfact is started. The search limit is \n" }{TEXT 207 60 "# choosen sup posing two factors find: 17*19, 23*29, 41*43,\n" }{TEXT 207 37 "# 71*7 3, 139*149, 283*293, 661*673.\n" }{TEXT 207 3 "#\n" }{TEXT 207 4 "> \n " }{TEXT 207 28 "> ifactor/ifact1st=proc(n)\n" }{TEXT 207 21 "> local \+ i,ig,r,sol;\n" }{TEXT 207 72 "> options remember,system,`Copyright 199 3 by Waterloo Maple Software`;\n" }{TEXT 207 17 "> sol := 1;\n" } {TEXT 207 15 "> r := n;\n" }{TEXT 207 34 "> for i to 7 while r <> 1 do\n" }{TEXT 207 80 "> ig := igcd(r,(323,765049,10589676 40189,9168346848864403802358641659,\n" }{TEXT 207 684 "> 34210 4831177853836844000918542910563842436194397212591435983889,79270988919 0322888122151467214412384719082407423339586081109312119937591689765999 3560023369901756756352260640974174268277959137341840564310562263449502 011246389,179121216345076044215350912828530796966835016565315142254527 4426966329577088681163508088417026575611445251431965793198643542697159 6067436404292477929139917856403646738338454540141395254935616183453275 6441918356224214016169612042405530047600574836123437652470013895386096 8227669770861596156638350957592746942206445542762469489659896584754267 1907558236641492154574341354887668197201554136418826500667651775965123 7727461023124369799987063929201186649\n" }{TEXT 207 18 "> )[i] );\n" }{TEXT 207 27 "> if ig <> 1 then\n" }{TEXT 207 32 "> \+ r := iquo(r,ig);\n" }{TEXT 207 72 "> while [323,6 67,1763,5183,20711,82919,444853][i] <= ig do\n" }{TEXT 207 73 "> \+ `ifactor/wheelfact`(ig,[17,23,41,71,139,283,661][i]);\n" } {TEXT 207 37 "> sol := sol*``(%);\n" }{TEXT 207 37 "> \+ ig := iquo(ig,%%)\n" }{TEXT 207 19 "> od; \n" }{TEXT 207 33 "> sol := sol*``(ig)\n" }{TEXT 207 14 "> fi\n" }{TEXT 207 11 "> od;\n" }{TEXT 207 11 "> sol\n" }{TEXT 207 6 "> end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "/*&I(ifactorG6$ %*protectedGI(_syslibG6\"\"\"\"I)ifact1stGF(!\"\"f*6#I\"nGF(6&I\"iGF(I #igGF(I\"rGF(I$solGF(6%I)rememberGF(I'systemGF&IJCopyright~1993~by~Wat erloo~Maple~SoftwareGF(F(C&>F3F)>F2F.?(F0F)F)\"\"(0F2F)C$>F1-I%igcdGF& 6$F2&6)\"$B$\"'\\]w\".*=Sw'*e5\"=f;keB!QSk)[oMo\"*\"jn*)Q)fV\"f7sR%>OC %Qc5Ha=4+Wo$Q&y@J463'eRLU2C3>ZQ7W@n9:A\"))GK!>*))4Fz\"jfl\\m=,#HR1()**zpV7 B5YFxB^'fx^wm+l#)=k8a:?(>ow)[NTVda@\\TmBev!>nUv%e'*)f'*[pCwUbW1A%pu#fd 4NQm:'fh3xpwAo4'Q&*Q,qClPM7O[d+w/IbSU?hph,9UAc$=>WcF`M=;c$\\D&RT,aa%Q$ Qnk.k&y\"*R\"HzZ#H/kVngfrpUNk)>$zl>V^_W6cdEqT)33N;\"o)3x&Hj'pUu_aA9:`c ;]$o'pzI&GG\"4N:U/w]M;77z\"6#F0@$0F1F)C%>F2-I%iquoGF&6$F2F1?(F(F)F)F(1 &7)FE\"$n'\"%j<\"%$=&\"&62#\"&>H)\"'`[WFLF1C%-I2ifactor/wheelfactGF'6$ F1&7)\"#<\"#B\"#T\"#r\"$R\"\"$$G\"$h'FL>F3*&F3F)-I!GF(6#I\"%GF(F)>F1-F R6$F1I#%%GF(>F3*&F3F)-Fho6#F1F)F3F(F(F(" }}{PARA 6 "" 1 "" {TEXT 207 4 "> \n" }{TEXT 207 4 "> \n" }{TEXT 207 3 "#\n" }{TEXT 207 54 "# This \+ routine find the prime factors with searcing.\n" }{TEXT 207 61 "# The \+ input is a positive integer known to have only factor\n" }{TEXT 207 24 "# between 17 and 1699.\n" }{TEXT 207 3 "#\n" }{TEXT 207 58 "# The \+ \"large searching\" here goes using gcd too, using\n" }{TEXT 207 58 "# intervals with length 30. The find gcd's larger then 1\n" }{TEXT 207 60 "# finally factored by a smaller search trying odd numbers.\n" } {TEXT 207 3 "#\n" }{TEXT 207 4 "> \n" }{TEXT 207 31 "> ifactor/wheelfa ct=proc(n,s)\n" }{TEXT 207 15 "> local i,ii;\n" }{TEXT 207 56 "> optio ns `Copyright 1993 by Waterloo Maple Software`;\n" }{TEXT 207 44 "> \+ for i from 30*iquo(s,30)+15 by 30 do\n" }{TEXT 207 16 "> i^2 ;\n" }{TEXT 207 60 "> if igcd(n,(%-4)*(%-16)*(%-64)*(%-196)) < > 1 then\n" }{TEXT 207 40 "> for ii from i-14 by 2 do\n" } {TEXT 207 57 "> if igcd(ii,n) <> 1 then RETURN(ii) fi \n" }{TEXT 207 18 "> od\n" }{TEXT 207 14 "> fi\n" }{TEXT 207 10 "> od\n" }{TEXT 207 6 "> end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "/*&I(ifactorG6$%*protectedGI(_syslibG6\"\"\"\"I*wheelfact GF(!\"\"f*6$I\"nGF(I\"sGF(6$I\"iGF(I#iiGF(6#IJCopyright~1993~by~Waterl oo~Maple~SoftwareGF(F(?(F1,&*&\"#IF)-I%iquoGF&6$F/F8F)F)\"#:F)F8F(I%tr ueGF&C$*$)F1\"\"#F)@$0-I%igcdGF&6$F.**,&I\"%GF(F)\"\"%F+F),&FIF)\"#;F+ F),&FIF)\"#kF+F),&FIF)\"$'>F+F)F)?(F2,&F1F)\"#9F+FAF(F=@$0-FE6$F2F.F)- I'RETURNGF&6#F2F(F(F(" }}{PARA 6 "" 1 "" {TEXT 207 4 "> \n" }{TEXT 207 4 "> \n" }{TEXT 207 3 "#\n" }{TEXT 207 46 "# This is the general e nd-factoring routine.\n" }{TEXT 207 49 "# The input is a positive inte ger containing no\n" }{TEXT 207 22 "# factor below 1700.\n" }{TEXT 207 3 "#\n" }{TEXT 207 49 "# If the number is less then 1709^2, then i t is\n" }{TEXT 207 56 "# a prime and simple returned. Otherwise the nu mber is\n" }{TEXT 207 52 "# tested and if it is found to be prime, ret urned.\n" }{TEXT 207 3 "#\n" }{TEXT 207 53 "# The second step is to tr y whether the numbers is \n" }{TEXT 207 44 "# a power using the routin e ifactor/power.\n" }{TEXT 207 3 "#\n" }{TEXT 207 51 "# The thierd ste p is to try Pollard's p-1 method.\n" }{TEXT 207 43 "# If there are cha nches then tried again.\n" }{TEXT 207 44 "# After the second failer or if no chances\n" }{TEXT 207 43 "# another version called ifactor/pp10 0000\n" }{TEXT 207 42 "# called to find factors p for which p-1\n" } {TEXT 207 34 "# has only factors below 100000.\n" }{TEXT 207 3 "#\n" } {TEXT 207 49 "# The last try is the procedure ifactor/bottom,\n" } {TEXT 207 48 "# which depends on the second input parameter.\n" }{TEXT 207 3 "#\n" }{TEXT 207 45 "# Finally, if no factor is found, then the \n" }{TEXT 207 53 "# routine returns with fail. Otherwise if is calle d\n" }{TEXT 207 55 "# for the factors found and returns with the produ ct.\n" }{TEXT 207 3 "#\n" }{TEXT 207 4 "> \n" }{TEXT 207 28 "> ifactor /ifact0th=proc(n)\n" }{TEXT 207 16 "> local sol,p;\n" }{TEXT 207 56 "> options `Copyright 1993 by Waterloo Maple Software`;\n" }{TEXT 207 45 "> if n < 2920681 then RETURN(``(n)) fi;\n" }{TEXT 207 44 "> \+ if isprime(n) then RETURN(``(n)) fi;\n" }{TEXT 207 38 "> sol := \+ `ifactor/power`(n,'p');\n" }{TEXT 207 65 "> if sol <> FAIL then RE TURN(`ifactor/ifact0th`(sol)^p) fi;\n" }{TEXT 207 41 "> sol := `if actor/pollp1`(n,13003);\n" }{TEXT 207 68 "> if sol = _tryagain the n sol := `ifactor/pollp1`(n,13004) fi;\n" }{TEXT 207 47 "> if sol \+ = _tryagain then sol := FAIL fi;\n" }{TEXT 207 59 "> if sol = FAIL then sol := `ifactor/pp100000`(n) fi;\n" }{TEXT 207 26 "> if sol \+ = FAIL then\n" }{TEXT 207 42 "> sol := `ifactor/bottom`(args); \n" }{TEXT 207 56 "> if not type(sol,integer) then RETURN(sol) fi\n" }{TEXT 207 11 "> fi;\n" }{TEXT 207 51 "> `ifactor/ifact 0th`(n/sol,args[2 .. nargs])*\n" }{TEXT 207 52 "> `ifactor/ifa ct0th`(sol,args[2 .. nargs])\n" }{TEXT 207 6 "> end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "/*&I(ifactorG6$%*protectedGI(_syslibG6\"\"\"\"I)ifact0 thGF(!\"\"f*6#I\"nGF(6$I$solGF(I\"pGF(6#IJCopyright~1993~by~Waterloo~M aple~SoftwareGF(F(C,@$2F.\"(\"o?H-I'RETURNGF&6#-I!GF(F-@$-I(isprimeGF( F-F8>F0-I.ifactor/powerGF(6$F..F1@$0F0I%FAILGF&-F96#)-I1ifactor/ifact0 thGF'6#F0F1>F0-I/ifactor/pollp1GF'6$F.\"&.I\"@$/F0I*_tryagainGF(>F0-FP 6$F.\"&/I\"@$FT>F0FG@$/F0FG>F0-I1ifactor/pp100000GF'F-@$FgnC$>F0-I/ifa ctor/bottomGF(6#%%argsG@$4-I%typeGF&6$F0I(integerGF&-F9FM*&-FL6$*&F.F) F0F+&Fao6#;\"\"#%&nargsGF)-FL6$F0F]pF)F(F(F(" }}{PARA 6 "" 1 "" {TEXT 207 4 "> \n" }{TEXT 207 4 "> \n" }{TEXT 207 3 "#\n" }{TEXT 207 48 "# T his small procedure check whether the input\n" }{TEXT 207 49 "# positi ve number is a prime power. It is known\n" }{TEXT 207 51 "# that there are no too small factors. The factor\n" }{TEXT 207 51 "# is given bac k and the exponent in the parameter\n" }{TEXT 207 8 "# 'p'.\n" }{TEXT 207 3 "#\n" }{TEXT 207 4 "> \n" }{TEXT 207 28 "> ifactor/power:=proc(n ,p)\n" }{TEXT 207 14 "> local i,r;\n" }{TEXT 207 56 "> options `Copyri ght 1993 by Waterloo Maple Software`;\n" }{TEXT 207 22 "> r := isq rt(n);\n" }{TEXT 207 45 "> if r^2 = n then p := 2; RETURN(r) fi;\n " }{TEXT 207 51 "> for i from 3 by 2 to iquo(length(n)+2,3) do\n" }{TEXT 207 43 "> if not isprime(i) then next fi;\n" }{TEXT 207 39 "> r := readlib('iroot')(n,i);\n" }{TEXT 207 48 "> \+ if r^i = n then p := i; RETURN(r) fi\n" }{TEXT 207 11 "> od;\n " }{TEXT 207 12 "> FAIL\n" }{TEXT 207 6 "> end;" }}{PARA 8 "" 1 "" {TEXT 208 43 "Error, invalid left hand side of assignment" }}{PARA 6 "" 1 "" {TEXT 207 4 "> \n" }{TEXT 207 4 "> \n" }{TEXT 207 3 "#\n" } {TEXT 207 51 "# This procedure try to find factors of the input\n" } {TEXT 207 50 "# positive integer n using Pollard's p-1 method.\n" } {TEXT 207 48 "# The second parameter is the base to find the\n" }{TEXT 207 12 "# factors.\n" }{TEXT 207 3 "#\n" }{TEXT 207 52 "# The base is in a cycle powered gradually to 2^9,\n" }{TEXT 207 42 "# 3^6*5^4*7^2* 11^2, 7*11*13^2*31^2*1229,\n" }{TEXT 207 51 "# 17^2*19^2*23^2*37*41*26 3, 29^2*43*47*53*83*443,\n" }{TEXT 207 43 "# ... 1699*1733*1741*1811*1 867*1907*1913.\n" }{TEXT 207 48 "# After each step the gcd of the powe r-1 and n\n" }{TEXT 207 47 "# is calculated. If the power was not 1, t hen\n" }{TEXT 207 45 "# this gcd is returned. If the power was 1,\n" } {TEXT 207 45 "# i.e. more factor steps in, then the power\n" }{TEXT 207 45 "# calculation is repeated in smaller steps.\n" }{TEXT 207 48 " # If this separates the factors, then a factor\n" }{TEXT 207 42 "# is \+ given back. Otherwise we try again.\n" }{TEXT 207 3 "#\n" }{TEXT 207 4 "> \n" }{TEXT 207 31 "> ifactor/pollp1=proc(n,seed)\n" }{TEXT 207 25 "> local d,i,k,primes,w;\n" }{TEXT 207 56 "> options `Copyright 199 3 by Waterloo Maple Software`;\n" }{TEXT 207 75 "> primes := [512, 2701400625,15369250897,22019225847811,3312226271377,\n" }{TEXT 207 68 "> 573380756513,9895915431937,9901032144937,26758334120513,\n" }{TEXT 207 76 "> 221345652736259,351896335286371,602532741650 737,705905813463569,\n" }{TEXT 207 81 "> 1146860257543171,1197 923438167619,4101182822350853,18093632169489029,\n" }{TEXT 207 66 "> \+ 15787341332349199,30541698536834113,32272865510432777,\n" } {TEXT 207 67 "> 90193223385948289,94859279632319593,2209578569 42948429,\n" }{TEXT 207 69 "> 217426779959284993,3538185221811 90721,419399945462884489,\n" }{TEXT 207 69 "> 5772441890673134 57,576566448802761223,635010439316635813,\n" }{TEXT 207 71 "> \+ 1163208606573930629,1274527543260713153,964201483442864677,\n" }{TEXT 207 72 "> 1189549054560841981,1730661029236703533,232452599686 0803761,\n" }{TEXT 207 72 "> 1749379074918976547,2379318098186 474761,3906310006235021863,\n" }{TEXT 207 72 "> 44000369329685 46433,3486357872137291841,4051550852530311307,\n" }{TEXT 207 72 "> \+ 7062924201913552913,9946204387896728657,9800419932800824021,\n" } {TEXT 207 75 "> 14016416453138321531,18451547056634890273,2077 0839191296803529,\n" }{TEXT 207 75 "> 23262237873880485889,282 82922465278428769,23779420029816701443,\n" }{TEXT 207 58 "> 29 006427360004220003,63229412132939686429249];\n" }{TEXT 207 13 "> s eed;\n" }{TEXT 207 32 "> for i to nops(primes) do\n" }{TEXT 207 39 "> modp(power(%,primes[i]),n);\n" }{TEXT 207 36 "> \+ if igcd(%-1,n) <> 1 then\n" }{TEXT 207 54 "> if % <> 1 the n RETURN(igcd(%-1,n)) fi;\n" }{TEXT 207 24 "> w := %%;\n" }{TEXT 207 53 "> d := numtheory[factorset](primes[i]);\n" }{TEXT 207 29 "> for k in d do\n" }{TEXT 207 44 "> \+ w := modp(power(w,k),n);\n" }{TEXT 207 33 "> \+ if w = 1 then\n" }{TEXT 207 79 "> if 1 < i then RE TURN(procname(n,modp(power(seed,k),n)))\n" }{TEXT 207 26 "> \+ fi\n" }{TEXT 207 66 "> elif igcd(w-1,n) <> 1 then RETURN(igcd(w-1,n))\n" }{TEXT 207 22 "> fi\n" } {TEXT 207 19 "> od;\n" }{TEXT 207 33 "> RETURN (_tryagain)\n" }{TEXT 207 14 "> fi\n" }{TEXT 207 11 "> od; \n" }{TEXT 207 12 "> FAIL\n" }{TEXT 207 6 "> end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "/*&I(ifactorG6$%*protectedGI(_syslibG6\"\"\"\"I'pollp 1GF(!\"\"f*6$I\"nGF(I%seedGF(6'I\"dGF(I\"iGF(I\"kGF(I'primesGF(I\"wGF( 6#IJCopyright~1993~by~Waterloo~Maple~SoftwareGF(F(C&>F47V\"$7&\"+D1S,F \",(*3Dp`\"\"/6y%eA>?#\".x8FEAJ$\"-8lv!Qt&\".P>V:f*)*\".P\\9K5!**\"/80 7M$en#\"0fit_cM@#\"0rjGNj*=N\"0P2lTF`-'\"0pNY8e!fq\"1rJad-'o9\"\"1>w;Q M#z>\"\"1`3NAG=,T\"2H!*[p@j$4=\"2*>\\BLTty:\"28T$o`)pT0$\"2xFV5b'GFK\" 2*G[fQBK>!*\"2$f>Bjz#f[*\"3H%[H%p&y&4A\"3$*\\Gf*znU<#\"3@2>\"=A&=QN\"3 *[%)GYX**R>%\"3dMJn!*=Wsd\"3B7w-)[kcw&\"38ej;$R/,N'\"4H1$Rd1'3K;\"\"4` JrgKaFXF\"\"3xY'GW$[,U'*\"4\")>%3ca!\\&*=\"\"4LNqO#H5mI<\"4hP!3'o*f_CB \"4Zl(*=\\2z$\\<\"4hZZ'=)4=$zB\"4j=-Ni+5j!R\"4LkaoH$p.+W\"4T=HP@(yN'[$ \"428JID&3b^S\"48Hb8>?CH1(\"4d'Gn*yQ/i%**\"4@S#3!G$*>/!)*\"5J:KQJX;k,9 \"5t-*[jcqa^%=\"5HN!oH\">R3x?\"5*)e[!)Q(yBiK#\"5p(G%y_YAHGG\"5V9q;)H+U zP#\"5.+A/+OFk+H\"8\\#HkoRH87%HK'F/?(F2F)F)-I%nopsGF&6#F4I%trueGF&C$-I %modpGF&6$-I&powerGF(6$I\"%GF(&F46#F2F.@$0-I%igcdGF&6$,&FepF)F)F+F.F)C '@$0FepF)-I'RETURNGF&6#Fjp>F5I#%%GF(>F1-&I*numtheoryGF(6#I*factorsetGF (6#Ffp?&F3F1F]pC$>F5-F`p6$-Fcp6$F5F3F.@&/F5F)@$2F)F2-Fbq6#-%)procnameG 6$F.-F`p6$-Fcp6$F/F3F.0-F[q6$,&F5F)F)F+F.F)-Fbq6#Fbs-Fbq6#I*_tryagainG F(I%FAILGF&F(F(F(" }}{PARA 6 "" 1 "" {TEXT 207 4 "> \n" }{TEXT 207 4 " > \n" }{TEXT 207 3 "#\n" }{TEXT 207 41 "# This procedure is a conterpa rt of the\n" }{TEXT 207 44 "# procedure above. Using the huge integers \n" }{TEXT 207 43 "# _prpr4000, _prpr10000, ... , _prpr94000\n" }{TEXT 207 52 "# which are products of primes from 4000 to 10000,\n" }{TEXT 207 43 "# from 10000 to 16000, etc. for which p-1\n" }{TEXT 207 48 "# \+ is not smooth, with the gcd method and using\n" }{TEXT 207 46 "# ifact or/wheelfract find these factors too.\n" }{TEXT 207 4 "# \n" }{TEXT 207 4 "> \n" }{TEXT 207 28 "> ifactor/pp100000=proc(n)\n" }{TEXT 207 12 "> local i;\n" }{TEXT 207 56 "> options `Copyright 1993 by Waterloo Maple Software`;\n" }{TEXT 207 43 "> for i from 4000 by 6000 to 9 4000 do\n" }{TEXT 207 28 "> igcd(_prpr.i,n);\n" }{TEXT 207 26 "> if % <> 1 then\n" }{TEXT 207 40 "> if % <> n th en RETURN(%)\n" }{TEXT 207 55 "> else RETURN(`ifactor/whee lfact`(n,i+1))\n" }{TEXT 207 18 "> fi\n" }{TEXT 207 14 "> \+ fi\n" }{TEXT 207 11 "> od;\n" }{TEXT 207 12 "> FAIL\n" }{TEXT 207 6 "> end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "/*&I(ifactorG6$ %*protectedGI(_syslibG6\"\"\"\"I)pp100000GF(!\"\"f*6#I\"nGF(6#I\"iGF(6 #IJCopyright~1993~by~Waterloo~Maple~SoftwareGF(F(C$?(F0\"%+S\"%+g\"&+S *I%trueGF&C$-I%igcdGF&6$-I\".GF(6$I&_prprGF(F0F.@$0I\"%GF(F)@%0FCF.-I' RETURNGF&6#FC-FG6#-I2ifactor/wheelfactGF'6$F.,&F0F)F)F)I%FAILGF&F(F(F( " }}{PARA 6 "" 1 "" {TEXT 207 4 "> \n" }{TEXT 207 4 "> \n" }{TEXT 207 3 "#\n" }{TEXT 207 51 "# The smallest constant used in ifactor/pp10000 0,\n" }{TEXT 207 18 "# as an example.\n" }{TEXT 207 3 "#\n" }{TEXT 207 4 "> \n" }{TEXT 207 84 "> _prpr4000:=99650580605048944632656882899 61456357240997208361983661053484670734\\\n" }{TEXT 207 177 "> 83901267 9433390148012701298284489624410640732766266494846161655447276888937196 6705406747239720527290803677864361380156879525642460435266474010399107 01757660785727431053299423;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\\zB%*H `5VFdygwv,2\"*R5SZm_VgCkD&zo:!QhV'yn.3HF0sRsu1aqm>P*))oFZalhh%[\\miwK2 k5Wi*[%G)H,F,[,RL%zE,R[tqY[`5m$)>O3s*4CdjXh**G)olKY%*[]g!e]'**" }} {PARA 6 "" 1 "" {TEXT 207 4 "> \n" }{TEXT 207 4 "> \n" }{TEXT 207 3 "# \n" }{TEXT 207 51 "# In the `easy` case no more further effort done.\n " }{TEXT 207 3 "#\n" }{TEXT 207 4 "> \n" }{TEXT 207 24 "> ifactor/easy =proc(n)\n" }{TEXT 207 64 "> options `Copyright 1993 by Waterl oo Maple Software`;\n" }{TEXT 207 26 "> _c.(length(n))\n" } {TEXT 207 6 "> end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "/*&I(ifactorG6$%* protectedGI(_syslibG6\"\"\"\"I%easyGF(!\"\"f*6#I\"nGF(F(6#IJCopyright~ 1993~by~Waterloo~Maple~SoftwareGF(F(-I\".GF(6$I#_cGF(-I'lengthGF&F-F(F (F(" }}{PARA 6 "" 1 "" {TEXT 207 4 "> \n" }{TEXT 207 3 "#\n" }{TEXT 207 38 "# This is the default procedure for \n" }{TEXT 207 39 "# facto rization of complicated cases.\n" }{TEXT 207 50 "# It use a variation \+ of the Morrison--Brillhard \n" }{TEXT 207 44 "# algorithm with continu ed fractions (??).\n" }{TEXT 207 3 "#\n" }{TEXT 207 4 "> \n" }{TEXT 207 28 "> ifactor/morrbril=proc(n)\n" }{TEXT 207 60 "> local i,j,A0,A1 ,Q0,Q1,PQ,iPQ,iPQc,g,r0,r1,qn,p,X,primes;\n" }{TEXT 207 48 "> global _ sq,_X2,_XX2,_Nprimes4,_Heap4,_Prpri;\n" }{TEXT 207 56 "> options `Copy right 1993 by Waterloo Maple Software`;\n" }{TEXT 207 21 "> _sq := '_sq';\n" }{TEXT 207 17 "> PQ := [];\n" }{TEXT 207 17 "> iPQ \+ := 1;\n" }{TEXT 207 18 "> iPQc := 1;\n" }{TEXT 207 52 "> useri nfo(1,ifactor,`ifactor final stage:`,n,\n" }{TEXT 207 77 "> lp rint(`Using a variation of the Morrison-Brillhart algorithm`));\n" } {TEXT 207 22 "> g := isqrt(n);\n" }{TEXT 207 36 "> if n < g^2 \+ then g := g-1 fi;\n" }{TEXT 207 78 "> X := isqrt(isqrt(isqrt(isqrt (10^(isqrt(iquo(599*length(n),4))-11)))));\n" }{TEXT 207 29 "> _X2 := min(X^2,20*X);\n" }{TEXT 207 22 "> _XX2 := X*_X2;\n" }{TEXT 207 56 "> userinfo(9,ifactor,'n' = n,'X' = X,'_X2' = _X2);\n" } {TEXT 207 23 "> primes[1] := 2;\n" }{TEXT 207 52 "> for _Nprim es4 while primes[_Nprimes4] < X do\n" }{TEXT 207 30 "> primes[ _Nprimes4];\n" }{TEXT 207 81 "> do nextprime(%); if modp(powe r(n,1/2*%-1/2),%) = 1 then break fi od;\n" }{TEXT 207 36 "> pr imes[_Nprimes4+1] := %\n" }{TEXT 207 11 "> od;\n" }{TEXT 207 15 "> p := 1;\n" }{TEXT 207 45 "> while p <= _Nprimes4 do p := 2*p od;\n" }{TEXT 207 17 "> p := p-1;\n" }{TEXT 207 44 "> for i f rom _Nprimes4-1 by -1 to 0 do\n" }{TEXT 207 14 "> 1;\n" }{TEXT 207 23 "> j := 2*i+1;\n" }{TEXT 207 62 "> while j < _ Nprimes4 do %%*_Heap4[j]; j := 2*j od;\n" }{TEXT 207 68 "> if p < j then primes[j-p] else primes[j-p+_Nprimes4] fi;\n" }{TEXT 207 30 "> _Heap4[i] := %%%*%\n" }{TEXT 207 11 "> od;\n" }{TEXT 207 33 "> _Prpri := 1440*_Heap4[0];\n" }{TEXT 207 16 "> A0 := 0;\n" }{TEXT 207 16 "> A1 := 1;\n" }{TEXT 207 16 "> Q1 := n; \n" }{TEXT 207 16 "> Q0 := 1;\n" }{TEXT 207 16 "> r1 := g;\n" }{TEXT 207 10 "> do\n" }{TEXT 207 39 "> qn := iquo(2*g-r1, Q0,'r0');\n" }{TEXT 207 35 "> A0 := modp(qn*A1+A0,n);\n" } {TEXT 207 32 "> Q1 := Q1+qn*(r0-r1);\n" }{TEXT 207 73 "> \+ if [qn,A0,r1] = PQ then RETURN(readlib(`ifactor/pollard`)(n))\n" } {TEXT 207 74 "> elif iPQc = iPQ then iPQ := 2*iPQ; PQ := [qn,A 0,r1]; iPQc := 1\n" }{TEXT 207 31 "> else iPQc := iPQc+1\n" } {TEXT 207 15 "> fi;\n" }{TEXT 207 36 "> analyze_resid( A0,-Q1,n);\n" }{TEXT 207 43 "> if % <> FAIL then RETURN(%) fi; \n" }{TEXT 207 39 "> qn := iquo(2*g-r0,Q1,'r1');\n" }{TEXT 207 35 "> A1 := modp(qn*A0+A1,n);\n" }{TEXT 207 38 "> \+ Q0 := Q0+qn*(r1-r0);\n" }{TEXT 207 35 "> analyze_resid(A 1,Q0,n);\n" }{TEXT 207 42 "> if % <> FAIL then RETURN(%) fi\n" }{TEXT 207 10 "> od\n" }{TEXT 207 6 "> end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "/*&I(ifactorG6$%*protectedGI(_syslibG6\"\"\"\"I)morrbrilG F(!\"\"f*6#I\"nGF(62I\"iGF(I\"jGF(I#A0GF(I#A1GF(I#Q0GF(I#Q1GF(I#PQGF(I $iPQGF(I%iPQcGF(I\"gGF(I#r0GF(I#r1GF(I#qnGF(I\"pGF(I\"XGF(I'primesGF(6 #IJCopyright~1993~by~Waterloo~Maple~SoftwareGF(F(C:>I$_sqGF(.FD>F67\"> F7F)>F8F)-I)userinfoGF&6'F)F$I5ifactor~final~stage:GF(F.-I'lprintGF&6# IVUsing~a~variation~of~the~Morrison-Brillhart~algorithmGF(>F9-I&isqrtG F&F-@$2F.*$)F9\"\"#F)>F9,&F9F)F)F+>F>-FT6#-FT6#-FT6#-FT6#)\"#5,&-FT6#- I%iquoGF&6$,$*&\"$*fF)-I'lengthGF&F-F)F)\"\"%F)\"#6F+>I$_X2GF(-I$minGF &6$*$)F>FYF),$*&\"#?F)F>F)F)>I%_XX2GF(*&F>F)F_pF)-FK6'\"\"*F$/.F.F./.F >F>/.F_pF_p>&F?6#F)FY?(I*_Nprimes4GF(F)F)F(2&F?6#FhqF>C%Fjq?(F(F)F)F(I %trueGF&C$-I*nextprimeGF(6#I\"%GF(@$/-I%modpGF&6$-I&powerGF(6$F.,&*&#F )FYF)FcrF)F)F^sF+FcrF)[>&F?6#,&FhqF)F)F)Fcr>F=F)?(F(F)F)F(1F=Fhq>F=,$* &FYF)F=F)F)>F=,&F=F)F)F+?(F0,&FhqF)F)F+F+\"\"!F^rC'F)>F1,&*&FYF)F0F)F) F)F)?(F(F)F)F(2F1FhqC$*&I#%%GF(F)&I'_Heap4GF(6#F1F)>F1,$*&FYF)F1F)F)@% 2F=F1&F?6#,&F1F)F=F+&F?6#,(F1F)F=F+FhqF)>&Fit6#F0*&I$%%%GF(F)FcrF)>I'_ PrpriGF(,$*&\"%S9F)&Fit6#F^tF)F)>F2F^t>F3F)>F5F.>F4F)>F;F9?(F(F)F)F(F^ rC->F<-Feo6%,&*&FYF)F9F)F)F;F+F4.F:>F2-Fgr6$,&*&FF5,&F 5F)*&FF7,$*&FYF)F7F)F)>F6FjwFI>F8,&F8F)F)F)-I.anal yze_residGF(6%F2,$F5F+F.@$0FcrI%FAILGF&-F\\xFbr>F<-Feo6%,&F]wF)F:F+F5. F;>F3-Fgr6$,&*&FF4,&F4F)*&F \n" } {TEXT 207 4 "> \n" }{TEXT 207 3 "#\n" }{TEXT 207 53 "# This subroutine works for the Morrison--Brillhard\n" }{TEXT 207 14 "# algorithm.\n" } {TEXT 207 3 "#\n" }{TEXT 207 4 "> \n" }{TEXT 207 30 "> analyze_resid=p roc(a,a2,n)\n" }{TEXT 207 29 "> local lrgpr,resid,base,g;\n" }{TEXT 207 15 "> global _sq;\n" }{TEXT 207 56 "> options `Copyright 1993 by W aterloo Maple Software`;\n" }{TEXT 207 16 "> abs(a2);\n" }{TEXT 207 23 "> igcd(%,_Prpri);\n" }{TEXT 207 23 "> while % <> 1 do \n" }{TEXT 207 68 "> iquo(%%,%); if _XX2 < % then RETURN(FAIL) fi; igcd(%,%%)\n" }{TEXT 207 11 "> od;\n" }{TEXT 207 41 "> if _X2 < %% then RETURN(FAIL) fi;\n" }{TEXT 207 20 "> lrgpr := %%;\n " }{TEXT 207 18 "> base := a;\n" }{TEXT 207 20 "> resid := a2; \n" }{TEXT 207 10 "> do\n" }{TEXT 207 34 "> igcd(resid,_He ap4[0]);\n" }{TEXT 207 39 "> g := igcd(iquo(resid,%),%);\n" } {TEXT 207 27 "> while g <> 1 do\n" }{TEXT 207 41 "> \+ resid := iquo(resid,g^2);\n" }{TEXT 207 39 "> base := mo dp(base/g,n);\n" }{TEXT 207 30 "> igcd(g,resid);\n" }{TEXT 207 42 "> g := igcd(%,iquo(resid,%))\n" }{TEXT 207 15 "> \+ od;\n" }{TEXT 207 29 "> if resid = 1 then\n" }{TEXT 207 72 "> if base <> 1 and base <> n-1 then RETURN(igcd(ba se-1,n))\n" }{TEXT 207 75 "> else userinfo(9,ifactor,`Bad \+ luck (+-1)^2=1`); RETURN(FAIL)\n" }{TEXT 207 18 "> fi\n" } {TEXT 207 15 "> fi;\n" }{TEXT 207 62 "> if lrgpr = 1 t hen lrgpr := lrgst_factor(resid) fi;\n" }{TEXT 207 78 "> useri nfo(9,ifactor,`*** factorable residue ***`,base,resid,lrgpr);\n" } {TEXT 207 40 "> if assigned(_sq[lrgpr]) then\n" }{TEXT 207 63 "> userinfo(9,ifactor,`----- collision at`,lrgpr);\n" } {TEXT 207 53 "> resid := resid*_sq[lrgpr][2]/lrgpr^2;\n" } {TEXT 207 57 "> base := modp(base*_sq[lrgpr][1]/lrgpr,n); \n" }{TEXT 207 26 "> lrgpr := 1\n" }{TEXT 207 57 "> \+ else _sq[lrgpr] := [base,resid]; RETURN(FAIL)\n" }{TEXT 207 14 "> \+ fi\n" }{TEXT 207 10 "> od\n" }{TEXT 207 6 "> end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "/I.analyze_residG6\"f*6%I\"aGF$I#a2GF$I\"nGF$6 &I&lrgprGF$I&residGF$I%baseGF$I\"gGF$6#IJCopyright~1993~by~Waterloo~Ma ple~SoftwareGF$F$C*-I$absG%*protectedG6#F(-I%igcdGF46$I\"%GF$I'_PrpriG F$?(F$\"\"\"FF+FB>F-F'>F,F(?(F$FF.-F76$-F@6$F,F9F9?(F$FF,-F@6 $F,*$)F.\"\"#F<>F--I%modpGF46$*&F-FF.-F76$F9Fhn@$/ F,F<@%30F-F<0F-,&F)FF+-I-lrg st_factorGF$6#F,-F\\q6(F^qF_qI;***~factorable~residue~***GF$F-F,F+@%-I )assignedGF46#&I$_sqGF$6#F+C&-F\\q6&F^qF_qI3-----~collision~atGF$F+>F, *(F,F<&F`r6#FboF<)F+FboFho>F--Feo6$*(F-F<&F`r6#FF+FF`r7 $F-F,FFF$6#FarF$" }}{PARA 6 "" 1 "" {TEXT 207 4 "> \n" }{TEXT 207 4 "> \n" }{TEXT 207 3 "#\n" }{TEXT 207 62 "# This is D. Shanks' undocument ed square-free factorization.\n" }{TEXT 207 3 "#\n" }{TEXT 207 4 "> \n " }{TEXT 207 26 "> ifactor/squfof=proc(a)\n" }{TEXT 207 25 "> local l,p,q,r,s,w;\n" }{TEXT 207 59 "> options `Copyright 1993 by Waterl oo Maple Software`;\n" }{TEXT 207 25 "> p := isqrt(a);\n" } {TEXT 207 39 "> if a < p^2 then p := p-1 fi;\n" }{TEXT 207 22 " > q := a-p^2;\n" }{TEXT 207 18 "> s := p;\n" }{TEXT 207 74 "> if q = 0 then RETURN(p) elif q = 1 then RETURN(squfof(2*a )) fi;\n" }{TEXT 207 29 "> l := 2*isqrt(2*s);\n" }{TEXT 207 13 "> do\n" }{TEXT 207 53 "> if q <= l then w[q/igcd(q, 2)] := 1 fi;\n" }{TEXT 207 34 "> p := s-modp(s+p,q);\n" } {TEXT 207 30 "> q := (a-p^2)/q;\n" }{TEXT 207 29 "> \+ r := isqrt(q);\n" }{TEXT 207 54 "> if q = r^2 and w[r] \+ <> 1 then break fi;\n" }{TEXT 207 53 "> if q <= l then w[q/ igcd(q,2)] := 1 fi;\n" }{TEXT 207 34 "> p := s-modp(s+p,q); \n" }{TEXT 207 29 "> q := (a-p^2)/q\n" }{TEXT 207 14 "> \+ od;\n" }{TEXT 207 32 "> p := p+r*iquo(s-p,r);\n" }{TEXT 207 26 "> q := (a-p^2)/r;\n" }{TEXT 207 13 "> do\n" } {TEXT 207 83 "> s-modp(s+%%,%); if % = %%% then RETURN(%%/i gcd(%%,2)) fi; (a-%^2)/%%\n" }{TEXT 207 13 "> od\n" }{TEXT 207 9 "> end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "/*&I(ifactorG6$%*protect edGI(_syslibG6\"\"\"\"I'squfofGF(!\"\"f*6#I\"aGF(6(I\"lGF(I\"pGF(I\"qG F(I\"rGF(I\"sGF(I\"wGF(6#IJCopyright~1993~by~Waterloo~Maple~SoftwareGF (F(C,>F1-I&isqrtGF&F-@$2F.*$)F1\"\"#F)>F1,&F1F)F)F+>F2,&F.F)F>F+>F4F1@ &/F2\"\"!-I'RETURNGF&6#F1/F2F)-FJ6#-F*6#,$*&F@F)F.F)F)>F0,$*&F@F)-F;6# ,$*&F@F)F4F)F)F)F)?(F(F)F)F(I%trueGF&C*@$1F2F0>&F56#*&F2F)-I%igcdGF&6$ F2F@F+F)>F1,&F4F)-I%modpGF&6$,&F4F)F1F)F2F+>F2*&FDF)F2F+>F3-F;6#F2@$3/ F2*$)F3F@F)0&F56#F3F)[FgnF`oFfo>F1,&F1F)*&F3F)-I%iquoGF&6$,&F4F)F1F+F3 F)F)>F2*&FDF)F3F+?(F(F)F)F(FenC%,&F4F)-Fco6$,&F4F)I#%%GF(F)I\"%GF(F+@$ /FdqI$%%%GF(-FJ6#*&FcqF)-F^o6$FcqF@F+*&,&F.F)*$)FdqF@F)F+F)FcqF+F(F(F( " }}{PARA 6 "" 1 "" {TEXT 207 4 "> \n" }{TEXT 207 4 "> \n" }{TEXT 207 3 "#\n" }{TEXT 207 39 "# This is J. M. Pollard's rho method.\n" }{TEXT 207 3 "#\n" }{TEXT 207 4 "> \n" }{TEXT 207 30 "> ifactor/pollard=proc (n,ex)\n" }{TEXT 207 17 "> local EX;\n" }{TEXT 207 60 "> optio ns `Copyright 1993 by Waterloo Maple Software`;\n" }{TEXT 207 37 "> \+ if nargs = 1 then EX := 2\n" }{TEXT 207 66 "> elif nargs <> 2 or not type(ex,integer) or ex < 2 then\n" }{TEXT 207 42 "> \+ ERROR(`invalid arguments`)\n" }{TEXT 207 25 "> else EX \+ := ex\n" }{TEXT 207 15 "> fi;\n" }{TEXT 207 14 "> 2;\n " }{TEXT 207 34 "> modp(power(%,EX)+1,n);\n" }{TEXT 207 14 "> \+ do\n" }{TEXT 207 39 "> modp(power(%%,EX)+1,n);\n" }{TEXT 207 51 "> modp(power(power(%%,EX)+1,EX)+1,n);\n" } {TEXT 207 40 "> if 1 < igcd(%%-%,n) then\n" }{TEXT 207 78 "> igcd(%%-%,n); if % = n then RETURN(FAIL) else RETUR N(%) fi\n" }{TEXT 207 18 "> fi\n" }{TEXT 207 15 "> \+ od;\n" }{TEXT 207 16 "> FAIL\n" }{TEXT 207 10 "> end;" }} {PARA 11 "" 1 "" {XPPMATH 20 "/*&I(ifactorG6$%*protectedGI(_syslibG6\" \"\"\"I(pollardGF(!\"\"f*6$I\"nGF(I#exGF(6#I#EXGF(6#IJCopyright~1993~b y~Waterloo~Maple~SoftwareGF(F(C'@'/%&nargsGF)>F1\"\"#550F7F94-I%typeGF &6$F/I(integerGF&2F/F9-I&ERRORGF&6#I2invalid~argumentsGF(>F1F/F9-I%mod pGF&6$,&-I&powerGF(6$I\"%GF(F1F)F)F)F.?(F(F)F)F(I%trueGF&C%-FI6$,&-FM6 $I#%%GF(F1F)F)F)F.-FI6$,&-FM6$FUF1F)F)F)F.@$2F)-I%igcdGF&6$,&FXF)FOF+F .C$Fjn@%/FOF.-I'RETURNGF&6#I%FAILGF&-Fbo6#FOFdoF(F(F(" }}{PARA 6 "" 1 "" {TEXT 207 4 "> \n" }{TEXT 207 4 "> \n" }{TEXT 207 3 "#\n" }{TEXT 207 44 "# This is Lenstra's elliptic curve method.\n" }{TEXT 207 3 "# \n" }{TEXT 207 4 "> \n" }{TEXT 207 27 "> ifactor/lenstra=proc(n)\n" } {TEXT 207 61 "> local i,s,prime,f,A,X,Z,rgen,sp,a,r,curves,B1,kg,k gg;\n" }{TEXT 207 60 "> options `Copyright 1993 by Waterloo Maple \+ Software`;\n" }{TEXT 207 82 "> if nargs < 1 or 3 < nargs then \+ ERROR(`wrong number of arguments.`) fi;\n" }{TEXT 207 66 "> if nargs < 3 then B1 := 1000000 else B1 := args[3] fi;\n" }{TEXT 207 69 "> if nargs < 2 then curves := 30 else curves := args[2] fi;\n " }{TEXT 207 47 "> if modp(n,2) = 0 then RETURN(2) fi;\n" } {TEXT 207 47 "> if modp(n,3) = 0 then RETURN(3) fi;\n" }{TEXT 207 43 "> s := evalf(1/2*sqrt(5)-1/2,30);\n" }{TEXT 207 36 "> \+ A := array(1 .. curves);\n" }{TEXT 207 36 "> X := arra y(1 .. curves);\n" }{TEXT 207 49 "> Z := array(1 .. curves,[1 \+ $ curves]);\n" }{TEXT 207 35 "> rgen := rand(1 .. n-1);\n" } {TEXT 207 30 "> for i to curves do\n" }{TEXT 207 23 "> \+ a := 0;\n" }{TEXT 207 56 "> while modp(a*(a^2-1)*(9*a ^2-1),n) = 0 do\n" }{TEXT 207 32 "> r := rgen();\n" } {TEXT 207 32 "> kg := r^2+6;\n" }{TEXT 207 38 "> \+ kgg := igcd(kg,n);\n" }{TEXT 207 52 "> if k gg <> 1 then RETURN(kgg) fi;\n" }{TEXT 207 39 "> a := \+ modp(6*r/kg,n)\n" }{TEXT 207 19 "> od;\n" }{TEXT 207 62 "> A[i] := modp(1/16*(-3*a^4-6*a^2+1)/a^3+1/2,n);\n" }{TEXT 207 37 "> X[i] := modp(3/4*a,n)\n" }{TEXT 207 15 "> \+ od;\n" }{TEXT 207 23 "> prime := 2;\n" }{TEXT 207 32 "> \+ while prime <= B1 do\n" }{TEXT 207 37 "> sp := round(s *prime);\n" }{TEXT 207 63 "> `ifactor/lenstra/mulpp`(1,n,A ,sp,prime,B1,X,Z);\n" }{TEXT 207 26 "> f := Z[1];\n" } {TEXT 207 41 "> for i from 2 to curves do\n" }{TEXT 207 67 "> `ifactor/lenstra/mulpp`(i,n,A,sp,prime,B1,X,Z); \n" }{TEXT 207 39 "> f := modp(f*Z[i],n)\n" }{TEXT 207 19 "> od;\n" }{TEXT 207 31 "> f := igcd(f, n);\n" }{TEXT 207 44 "> if f <> 1 then RETURN(f) fi;\n" } {TEXT 207 41 "> prime := nextprime(prime)\n" }{TEXT 207 15 "> od;\n" }{TEXT 207 16 "> FAIL\n" }{TEXT 207 10 "> end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "/*&I(ifactorG6$%*protectedG I(_syslibG6\"\"\"\"I(lenstraGF(!\"\"f*6#I\"nGF(61I\"iGF(I\"sGF(I&prime GF(I\"fGF(I\"AGF(I\"XGF(I\"ZGF(I%rgenGF(I#spGF(I\"aGF(I\"rGF(I'curvesG F(I#B1GF(I#kgGF(I$kggGF(6#IJCopyright~1993~by~Waterloo~Maple~SoftwareG F(F(C0@$52%&nargsGF)2\"\"$FE-I&ERRORGF&6#I;wrong~number~of~arguments.G F(@%2FEFG>F<\"(+++\">F<&%%argsG6#FG@%2FE\"\"#>F;\"#I>F;&FR6#FV@$/-I%mo dpGF&6$F.FV\"\"!-I'RETURNGF&Fen@$/-Fin6$F.FGF[o-F]oFS>F1-I&evalfGF&6$, &*&#F)FVF)-I%sqrtGF(6#\"\"&F)F)FioF+FX>F4-I&arrayGF&6#;F)F;>F5F_p>F6-F `p6$Fbp7#-I\"$GF&6$F)F;>F7-I%randGF(6#;F),&F.F)F)F+?(F0F)F)F;I%trueGF& C&>F9F[o?(F(F)F)F(/-Fin6$*(F9F),&*$)F9FVF)F)F)F+F),&*&\"\"*F)F\\rF)F)F )F+F)F.F[oC'>F:-F7F(>F=,&*$)F:FVF)F)\"\"'F)>F>-I%igcdGF&6$F=F.@$0F>F)- F]o6#F>>F9-Fin6$,$*(FgrF)F:F)F=F+F)F.>&F46#F0-Fin6$,&*(#F)\"#;F),(*&FG F))F9\"\"%F)F+*&FgrF)F\\rF)F+F)F)F))F9FGF+F)FioF)F.>&F5Fgs-Fin6$,$*&#F GFatF)F9F)F)F.>F2FV?(F(F)F)F(1F2FF8-I&roundGF(6#*&F1F)F2F)-I6ifact or/lenstra/mulppGF(6*F)F.F4F8F2FF3&F66#F)?(F0FVF)F;FbqC$-Feu6*F0 F.F4F8F2FF3-Fin6$*&F3F)&F6FgsF)F.>F3-Fjr6$F3F.@$0F3F)-F]o6#F3>F2 -I*nextprimeGF(6#F2I%FAILGF&F(F(F(" }}{PARA 6 "" 1 "" {TEXT 207 4 "> \+ \n" }{TEXT 207 4 "> \n" }{TEXT 207 3 "#\n" }{TEXT 207 50 "# This subro utine the multiplications on a given\n" }{TEXT 207 19 "# elliptic curv e.\n" }{TEXT 207 3 "#\n" }{TEXT 207 4 "> \n" }{TEXT 207 50 "> ifactor/ lenstra/mulpp=proc(i,n,A,mm,nn,B1,X,Z)\n" }{TEXT 207 20 "> local pow,a x,az;\n" }{TEXT 207 56 "> options `Copyright 1993 by Waterloo Maple So ftware`;\n" }{TEXT 207 19 "> ax := X[i];\n" }{TEXT 207 19 "> a z := Z[i];\n" }{TEXT 207 18 "> pow := nn;\n" }{TEXT 207 26 "> \+ while pow <= B1 do\n" }{TEXT 207 81 "> `ifactor/lenstra/ellmul `(n,A[i],mm,nn,ax,az,'ax','az'); pow := pow*nn\n" }{TEXT 207 11 "> \+ od;\n" }{TEXT 207 19 "> X[i] := ax;\n" }{TEXT 207 18 "> Z[i] \+ := az\n" }{TEXT 207 6 "> end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "/*(I(if actorG6$%*protectedGI(_syslibG6\"\"\"\"I(lenstraGF(!\"\"I&mulppGF(F+f* 6*I\"iGF(I\"nGF(I\"AGF(I#mmGF(I#nnGF(I#B1GF(I\"XGF(I\"ZGF(6%I$powGF(I# axGF(I#azGF(6#IJCopyright~1993~by~Waterloo~Maple~SoftwareGF(F(C(>F9&F5 6#F/>F:&F6F@>F8F3?(F(F)F)F(1F8F4C$-I7ifactor/lenstra/ellmulGF(6*F0&F1F @F2F3F9F:.F9.F:>F8*&F8F)F3F)>F?F9>FBF:F(F(F(" }}{PARA 6 "" 1 "" {TEXT 207 4 "> \n" }{TEXT 207 4 "> \n" }{TEXT 207 3 "#\n" }{TEXT 207 42 "# T his procedure do some multiplications\n" }{TEXT 207 25 "# on an ellipt ic curve.\n" }{TEXT 207 3 "#\n" }{TEXT 207 4 "> \n" }{TEXT 207 56 "> i factor/lenstra/ellmul=proc(n,A,mm,nn,px,pz,aax,aaz)\n" }{TEXT 207 48 " > local ax,az,bx,bz,cx,cz,tmpx,tmpz,d,e,t1,t2;\n" }{TEXT 207 56 "> opt ions `Copyright 1993 by Waterloo Maple Software`;\n" }{TEXT 207 17 "> \+ cx := px;\n" }{TEXT 207 17 "> cz := pz;\n" }{TEXT 207 16 "> \+ e := mm;\n" }{TEXT 207 19 "> d := nn-mm;\n" }{TEXT 207 21 "> \+ if e < d then\n" }{TEXT 207 59 "> `ifactor/lenstra/elldoub`(n ,A,px,pz,'bx','bz');\n" }{TEXT 207 21 "> ax := px;\n" }{TEXT 207 21 "> az := pz;\n" }{TEXT 207 20 "> d := d-e\n" } {TEXT 207 12 "> else\n" }{TEXT 207 59 "> `ifactor/lenstra/ elldoub`(n,A,px,pz,'ax','az');\n" }{TEXT 207 21 "> bx := px;\n " }{TEXT 207 21 "> bz := pz;\n" }{TEXT 207 20 "> e := \+ e-d\n" }{TEXT 207 11 "> fi;\n" }{TEXT 207 23 "> while e <> 0 d o\n" }{TEXT 207 25 "> if e < d then\n" }{TEXT 207 27 "> \+ tmpx := bx;\n" }{TEXT 207 27 "> tmpz := bz;\n" } {TEXT 207 46 "> t1 := modp((ax-az)*(bx+bz),n);\n" }{TEXT 207 46 "> t2 := modp((ax+az)*(bx-bz),n);\n" }{TEXT 207 51 "> bx := modp(cz*modp((t1+t2)^2,n),n);\n" }{TEXT 207 51 "> bz := modp(cx*modp((t1-t2)^2,n),n);\n" }{TEXT 207 24 "> \+ d := d-e\n" }{TEXT 207 16 "> else\n" }{TEXT 207 27 "> tmpx := ax;\n" }{TEXT 207 27 "> tmpz := az; \n" }{TEXT 207 46 "> t1 := modp((ax-az)*(bx+bz),n);\n" } {TEXT 207 46 "> t2 := modp((ax+az)*(bx-bz),n);\n" }{TEXT 207 51 "> ax := modp(cz*modp((t1+t2)^2,n),n);\n" }{TEXT 207 51 "> az := modp(cx*modp((t1-t2)^2,n),n);\n" }{TEXT 207 24 "> e := e-d\n" }{TEXT 207 15 "> fi;\n" } {TEXT 207 23 "> cx := tmpx;\n" }{TEXT 207 22 "> cz := \+ tmpz\n" }{TEXT 207 11 "> od;\n" }{TEXT 207 18 "> aax := ax;\n" }{TEXT 207 17 "> aaz := az\n" }{TEXT 207 6 "> end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "/*(I(ifactorG6$%*protectedGI(_syslibG6\"\"\"\"I(len straGF(!\"\"I'ellmulGF(F+f*6*I\"nGF(I\"AGF(I#mmGF(I#nnGF(I#pxGF(I#pzGF (I$aaxGF(I$aazGF(6.I#axGF(I#azGF(I#bxGF(I#bzGF(I#cxGF(I#czGF(I%tmpxGF( I%tmpzGF(I\"dGF(I\"eGF(I#t1GF(I#t2GF(6#IJCopyright~1993~by~Waterloo~Ma ple~SoftwareGF(F(C*>FF=F4>FAF1>F@,&F2F)F1F+@%2FAF@C&-I8ifactor/len stra/elldoubGF(6(F/F0F3F4.F:.F;>F8F3>F9F4>F@,&F@F)FAF+C&-FP6(F/F0F3F4. F8.F9>F:F3>F;F4>FA,&FAF)F@F+?(F(F)F)F(0FA\"\"!C%@%FMC)>F>F:>F?F;>FB-I% modpGF&6$*&,&F8F)F9F+F),&F:F)F;F)F)F/>FC-Feo6$*&,&F8F)F9F)F),&F:F)F;F+ F)F/>F:-Feo6$*&F=F)-Feo6$*$),&FBF)FCF)\"\"#F)F/F)F/>F;-Feo6$*&FF>F8>F?F9FcoFjo>F8Fap>F9F[qFin>F>F=F ?>F5F8>F6F9F(F(F(" }}{PARA 6 "" 1 "" {TEXT 207 4 "> \n" }{TEXT 207 4 " > \n" }{TEXT 207 3 "#\n" }{TEXT 207 55 "# This procedure do a doubling on the elliptic curve.\n" }{TEXT 207 3 "#\n" }{TEXT 207 4 "> \n" } {TEXT 207 49 "> ifactor/lenstra/elldoub=proc(n,A,ax,az,cx,cz)\n" } {TEXT 207 16 "> local t1,t2;\n" }{TEXT 207 56 "> options `Copyright 19 93 by Waterloo Maple Software`;\n" }{TEXT 207 32 "> t1 := modp((ax +az)^2,n);\n" }{TEXT 207 32 "> t2 := modp((ax-az)^2,n);\n" }{TEXT 207 28 "> cx := modp(t1*t2,n);\n" }{TEXT 207 50 "> cz := modp( (t1-t2)*modp(A*(t1-t2)+t2,n),n)\n" }{TEXT 207 6 "> end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "/*(I(ifactorG6$%*protectedGI(_syslibG6\"\"\"\"I(len straGF(!\"\"I(elldoubGF(F+f*6(I\"nGF(I\"AGF(I#axGF(I#azGF(I#cxGF(I#czG F(6$I#t1GF(I#t2GF(6#IJCopyright~1993~by~Waterloo~Maple~SoftwareGF(F(C& >F6-I%modpGF&6$*$),&F1F)F2F)\"\"#F)F/>F7-F=6$*$),&F1F)F2F+FBF)F/>F3-F= 6$*&F6F)F7F)F/>F4-F=6$*&,&F6F)F7F+F)-F=6$,&*&F0F)FQF)F)F7F)F/F)F/F(F(F (" }}{PARA 6 "" 1 "" {TEXT 207 4 "> \n" }{TEXT 207 4 "> \n" }{TEXT 207 2 "> " }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 9 "2.4. A pr" }{TEXT 206 8 "\303\255" }{TEXT 206 5 "moszt" }{TEXT 206 8 "\303\263" }{TEXT 206 8 "k eloszl" }{TEXT 206 8 "\303\241" }{TEXT 206 1 "s" }{TEXT 206 8 "\303\241" }{TEXT 206 1 "r" }{TEXT 206 8 "\303\263" }{TEXT 206 2 "l. " }}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 9 "2.5. A pr" }{TEXT 206 8 "\30 3\255" }{TEXT 206 5 "moszt" }{TEXT 206 8 "\303\263" }{TEXT 206 4 "k sz " }{TEXT 206 8 "\303\241" }{TEXT 206 1 "m" }{TEXT 206 8 "\303\241" } {TEXT 206 7 "nak hat" }{TEXT 206 8 "\303\241" }{TEXT 206 7 "reloszl" } {TEXT 206 8 "\303\241" }{TEXT 206 3 "sa." }}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 13 "2.6. Fermat m" }{TEXT 206 8 "\303\263" }{TEXT 206 7 "dsz ere." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 48 "# This procedure prepare the si eve table S for\n" }{MPLTEXT 1 0 56 "# Fermat's factorization procedur e. Parameter n is the\n" }{MPLTEXT 1 0 52 "# integer to factor and m i s the vector of moduli.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 53 "preparefermatsieve:=proc(n,S,m) local i,j,k,x2,x2n; \n" }{MPLTEXT 1 0 24 "x2:=table; x2n:=table;\n" }{MPLTEXT 1 0 21 "for \+ i to nops(m) do\n" }{MPLTEXT 1 0 44 " for j from 0 to m[i]-1 do S[i,j ]:=0; od;\n" }{MPLTEXT 1 0 29 " for j from 0 to m[i]-1 do\n" } {MPLTEXT 1 0 26 " x2[j]:=j^2 mod m[i];\n" }{MPLTEXT 1 0 29 " x2n [j]:=j^2-n mod m[i];\n" }{MPLTEXT 1 0 7 " od;\n" }{MPLTEXT 1 0 29 " \+ for j from 0 to m[i]-1 do\n" }{MPLTEXT 1 0 31 " for k from 0 to m[i ]-1 do\n" }{MPLTEXT 1 0 42 " if x2n[j]=x2[k] then S[i,j]:=1 fi;\n " }{MPLTEXT 1 0 9 " od;\n" }{MPLTEXT 1 0 15 " od; \n" } {MPLTEXT 1 0 8 "od; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"nG6\" I\"SGF%I\"mGF%6'I\"iGF%I\"jGF%I\"kGF%I#x2GF%I$x2nGF%F%F%C%>F,I&tableG% *protectedG>F-F0?(F)\"\"\"F4-I%nopsGF16#F'I%trueGF1C%?(F*\"\"!F4,&&F'6 #F)F4F4!\"\"F8>&F&6$F)F*F;?(F*F;F4F&F,6#F*-I$modGF%6$*$)F*\"\"#F 4F=>&F-FG-FI6$,&FKF4F$F?F=?(F*F;F4FFAF4F%F %F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 40 "# This procedure do factorization with\n" }{MPLTEXT 1 0 35 "# Ferm at's method. Parameter n is\n" }{MPLTEXT 1 0 57 "# the odd number to f actor and m is the list of moduli.\n" }{MPLTEXT 1 0 41 "# Returns with u where u is the largest\n" }{MPLTEXT 1 0 46 "# factor of n less then or equal to sqrt(n).\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" } {MPLTEXT 1 0 54 "fermatfactorization:=proc(n::posint,m::list(posint)) \n" }{MPLTEXT 1 0 22 "local k,x,y,i,S,r,f;\n" }{MPLTEXT 1 0 63 "if typ e(n,even) then error \"first argument must be odd\" fi;\n" }{MPLTEXT 1 0 52 "S:=table(); preparefermatsieve(n,S,m); r:=nops(m);\n" } {MPLTEXT 1 0 30 "k:=array(1..r); x:=isqrt(n);\n" }{MPLTEXT 1 0 38 "for i to r do k[i]:=-x mod m[i]; od;\n" }{MPLTEXT 1 0 15 "while true do\n " }{MPLTEXT 1 0 12 " f:=true;\n" }{MPLTEXT 1 0 63 " for i to r do if S[i,k[i]]<>1 then f:=false; break; fi; od;\n" }{MPLTEXT 1 0 13 " if \+ f then\n" }{MPLTEXT 1 0 22 " y:=isqrt(x^2-n);\n" }{MPLTEXT 1 0 39 " if y^2=x^2-n then RETURN(x-y) fi;\n" }{MPLTEXT 1 0 7 " fi;\n" } {MPLTEXT 1 0 11 " x:=x+1;\n" }{MPLTEXT 1 0 44 " for i to r do k[i]:= k[i]-1 mod m[i]; od;\n" }{MPLTEXT 1 0 8 "od; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6$'I\"nG6\"I'posintG%*protectedG'I\"mGF&-I%listGF(6#F'6 )I\"kGF&I\"xGF&I\"yGF&I\"iGF&I\"SGF&I\"rGF&I\"fGF&F&F&C*@$-I%typeGF(6$ F%I%evenGF(YQ;first~argument~must~be~oddF&>F3-I&tableGF(F&-I3preparefe rmatsieveGF&6%F%F3F*>F4-I%nopsGF(6#F*>F/-I&arrayGF(6#;\"\"\"F4>F0-I&is qrtGF(6#F%?(F2FMFMF4I%trueGF(>&F/6#F2-I$modGF&6$,$F0!\"\"&F*FV?(F&FMFM F&FSC'>F5FS?(F2FMFMF4FS@$0&F36$F2FUFMC$>F5I&falseGF([@$F5C$>F1-FP6#,&* $)F0\"\"#FMFMF%Fen@$/*$)F1F[pFMFho-I'RETURNGF(6#,&F0FMF1Fen>F0,&F0FMFM FM?(F2FMFMF4FS>FU-FX6$,&FUFMFMFenFfnF&F&F&" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 29 "debug(fermatfactorization);\n" }{MPLTEXT 1 0 40 "fe rmatfactorization(13*17,[3,5,7,8,11]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "I4fermatfactorizationG6\"" }}{PARA 9 "" 1 "" {TEXT 209 61 "\{--> ent er fermatfactorization, args = 221, [3, 5, 7, 8, 11]" }}{PARA 11 "" 1 "" {XPPMATH 20 "=6\"I&falseG%*protectedGE\\[l!" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "=6\"6#;\"\"\"\"\"& E\\[l!" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#:" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "I %trueG%*protectedG" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 9 " " 1 "" {TEXT 209 54 "<-- exit fermatfactorization (now at top level) = 13\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#8" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "undebug(fermatfactorization);\n" }{MPLTEXT 1 0 40 "fermatfactorization(11111,[3,5,7,8,11]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "I4fermatfactorizationG6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#T" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 13 "2.7. Feladat." }} {PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "interface(echo=3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 53 "# This procedure do factorization with addition and\n" }{MPLTEXT 1 0 52 "# s ubstraction. Returns with the largest factor of\n" }{MPLTEXT 1 0 47 "# odd number n less then or equal to sqrt(n).\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 38 "addsubfactor:=proc(n) local xp, yp,r;\n" }{MPLTEXT 1 0 57 "if type(n,even) then error \"argument must \+ be odd\" fi;\n" }{MPLTEXT 1 0 48 "isqrt(n); xp:=2*%+1; r:=%%^2 -n; yp:=1;\n" }{MPLTEXT 1 0 15 "while true do\n" }{MPLTEXT 1 0 38 " w hile r>0 do r:=r-yp; yp:=yp+2 od;\n" }{MPLTEXT 1 0 36 " if r=0 then r eturn (xp-yp)/2 fi;\n" }{MPLTEXT 1 0 22 " r:=r+xp; xp:=xp+2;\n" } {MPLTEXT 1 0 8 "od; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6#I\"nG6\" 6%I#xpGF%I#ypGF%I\"rGF%F%F%C(@$-I%typeG%*protectedG6$F$I%evenGF.YQ5arg ument~must~be~oddF%-I&isqrtGF.F#>F',&*&\"\"#\"\"\"I\"%GF%F9F9F9F9>F),& *$)I#%%GF%F8F9F9F$!\"\">F(F9?(F%F9F9F%I%trueGF.C&?(F%F9F9F%2\"\"!F)C$> F),&F)F9F(F@>F(,&F(F9F8F9@$/F)FGO,&*&#F9F8F9F'F9F9*&FRF9F(F9F@>F),&F)F 9F'F9>F',&F'F9F8F9F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "debug(addsubfactor); addsubfactor(111);" }}{PARA 11 "" 1 "" {XPPMATH 20 "I-addsubfactorG6\"" }}{PARA 9 "" 1 "" {TEXT 209 36 "\{--> enter ad dsubfactor, args = 111" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#6" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#B" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#5" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"(" }} {PARA 11 "" 1 "" {XPPMATH 20 "!\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "\" \"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#<" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#D" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\")" }}{PARA 11 " " 1 "" {XPPMATH 20 "\"#6" }}{PARA 11 "" 1 "" {XPPMATH 20 "!\"$" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"#8" }}{PARA 11 "" 1 "" {XPPMATH 20 "\" #A" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#F" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#:" }}{PARA 11 "" 1 "" {XPPMATH 20 "!\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#<" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#@" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#H" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"#>" }}{PARA 11 "" 1 "" {XPPMATH 20 "!#:" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#@" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#9" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#J" }}{PARA 11 "" 1 "" {XPPMATH 20 "!\"(" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"#B" }}{PARA 11 "" 1 "" {XPPMATH 20 "\" #C" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#L" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#D" }}{PARA 11 "" 1 "" {XPPMATH 20 "!#C" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#F" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#N" }} {PARA 11 "" 1 "" {XPPMATH 20 "!#=" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"# H" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#<" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#P" }}{PARA 11 "" 1 "" {XPPMATH 20 "!#7" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#J" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#D" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#R" }}{PARA 11 "" 1 "" {XPPMATH 20 "!\"'" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"#L" }}{PARA 11 "" 1 "" {XPPMATH 20 "\" #L" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#T" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#N" }}{PARA 9 "" 1 "" {TEXT 209 46 "<-- exit addsubfactor (now at top level) = 3\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 71 "undebug(addsubfactor); addsubfactor(6463); addsubfactor(999863*9 99883);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#B" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'j)***" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 13 "2.8. \+ Feladat." }}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 31 "2.9. Pollard \317\2 61 m\303\263" }{TEXT 206 7 "dszere." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{PARA 0 "" 0 "" {TEXT 201 7 "Az n sz" }{TEXT 201 8 "\303\241" }{TEXT 201 5 "m has" }{TEXT 201 8 "\303\255" }{TEXT 201 1 "t" }{TEXT 201 8 " \303\241" }{TEXT 201 16 "sa az x->x^2+c f" }{TEXT 201 8 "\303\274" } {TEXT 201 3 "ggv" }{TEXT 201 8 "\303\251" }{TEXT 201 11 "ny felhaszn" }{TEXT 201 8 "\303\241" }{TEXT 201 1 "l" }{TEXT 201 8 "\303\241" } {TEXT 201 1 "s" }{TEXT 201 8 "\303\241" }{TEXT 201 15 "val; g egy iter " }{TEXT 201 8 "\303\241" }{TEXT 201 2 "ci" }{TEXT 201 8 "\303\263" } {TEXT 201 7 "csoport" }}{PARA 0 "" 0 "" {TEXT 201 1 "m" }{TEXT 201 8 " \303\251" }{TEXT 201 5 "rete " }{TEXT 201 8 "\303\251" }{TEXT 201 32 " s legfeljebb maxgs csoport fog v" }{TEXT 201 8 "\303\251" }{TEXT 201 7 "grehajt" }{TEXT 201 8 "\303\263" }{TEXT 201 4 "dni." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 68 "pollard rhosplit:=proc(n::posint,c::posint,g::posint,maxgs::posint)\n" } {MPLTEXT 1 0 37 "local x,xx,xp,xo,xpo,i,j,k,ko,l,lo;\n" }{MPLTEXT 1 0 47 "x:=1+c mod n; xp:=1; i:=0; k:=1; l:=1; xx:=1;\n" }{MPLTEXT 1 0 35 "while igcd(xx,n)=1 and iF0-I$ modGF&6$,&\"\"\"FAF*FAF%>F2FA>F5\"\"!>F7FA>F9FA>F1FA?(F&FAFAF&3/-I%igc dGF(6$F1F%FA2F5F.C*>F3F0>F4F2>F8F7>F:F9>F6FDFG?(F&FAFAF&2F6F,C'>F1-F>6 $*&F1FA,&F2FAF0!\"\"FAF%>F7,&F7FAFAFgn@$/F7FDC%>F2F0>F7F9>F9,$*&\"\"#F AF9FAFA>F0-F>6$,&*$)F0FboFAFAF*FAF%>F6,&F6FAFAFA>F5,&F5FAFAFA@$2FKF%OF K>F0F3>F2F4>F7F8>F9F:FT?(F&FAFAF&3/-FL6$FfnF%FAFVC&FhnFjnFcoFioFgpF&F& F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "pollardrhosplit(99986 3*999883,1,2^4,2^5);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'j)***" }}}} {SECT 1 {PARA 4 "" 0 "" {TEXT 206 14 "2.10. Feladat." }}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 14 "2.11. Fermat t" }{TEXT 206 8 "\303\251" }{TEXT 206 5 "tele." }}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 13 "2.12. Eu ler t" }{TEXT 206 8 "\303\251" }{TEXT 206 5 "tele." }}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 7 "2.13. K" }{TEXT 206 8 "\303\255" }{TEXT 206 9 "n ai marad" }{TEXT 206 8 "\303\251" }{TEXT 206 2 "kt" }{TEXT 206 8 "\303 \251" }{TEXT 206 4 "tel." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "chrem([1,2,2],[2,3,7]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#B" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 7 "2 .14. T" }{TEXT 206 8 "\303\251" }{TEXT 206 4 "tel." }}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 16 "2.15. Gyors hatv" }{TEXT 206 8 "\303\241" } {TEXT 206 4 "nyoz" }{TEXT 206 8 "\303\241" }{TEXT 206 2 "s." }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n " }{MPLTEXT 1 0 37 "# Calculation of modular power of a\n" }{MPLTEXT 1 0 41 "# with the left-to-right binary method.\n" }{MPLTEXT 1 0 3 "# \n" }{MPLTEXT 1 0 3 " \n" }{MPLTEXT 1 0 60 "left2right:=proc(a,e::posi nt,mult::procedure) local b,x,n;\n" }{MPLTEXT 1 0 29 "b:=convert(e,bas e,2); x:=a;\n" }{MPLTEXT 1 0 36 "for n from nops(b)-1 by -1 to 1 do\n" }{MPLTEXT 1 0 17 " x:=mult(x,x);\n" }{MPLTEXT 1 0 36 " if b[n]>0 th en x:=mult(x,a); fi;\n" }{MPLTEXT 1 0 11 "od; x; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6%I\"aG6\"'I\"eGF%I'posintG%*protectedG'I%multGF%I* procedureGF)6%I\"bGF%I\"xGF%I\"nGF%F%F%C&>F.-I(convertGF)6%F'I%baseGF% \"\"#>F/F$?(F0,&-I%nopsGF)6#F.\"\"\"F>!\"\"F?F>I%trueGF)C$>F/-F+6$F/F/ @$2\"\"!&F.6#F0>F/-F+6$F/F$F/F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "debug(left2right); left2right(2,11,(x,y)->x*y);" }} {PARA 11 "" 1 "" {XPPMATH 20 "I+left2rightG6\"" }}{PARA 9 "" 1 "" {TEXT 209 87 "\{--> enter left2right, args = 2, 11, proc (x, y) option s operator, arrow; x*y end proc" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\" \"\"F#\"\"!F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#K" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"%C5" } }{PARA 11 "" 1 "" {XPPMATH 20 "\"%[?" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"%[?" }}{PARA 9 "" 1 "" {TEXT 209 47 "<-- exit left2right (now at top level) = 2048\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"%[?" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 35 "# Calculation of a modular power \n" }{MPLTEXT 1 0 42 "# with the left-to-right 2^m -ary method.\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 54 "fastexp:=proc(a,e::posint,m::posint,mult::procedure)\n" } {MPLTEXT 1 0 25 "local i,j,k,P,x,b,aa,n;\n" }{MPLTEXT 1 0 66 "b:=conve rt(e,base,2); n:=nops(b)-1; x:=a; P:=[a]; aa:=mult(a,a);\n" }{MPLTEXT 1 0 64 "for j from 2 to 2^(m-1) do P:=[op(P),mult(P[nops(P)],aa)]; od; \n" }{MPLTEXT 1 0 15 "while true do\n" }{MPLTEXT 1 0 29 " if n=0 then return(x) fi;\n" }{MPLTEXT 1 0 50 " if b[n]=0 then x:=mult(x,x); n:= n-1; next; fi;\n" }{MPLTEXT 1 0 43 " i:=1; j:=1; k:=0; x:=mult(x,x); \+ n:=n-1;\n" }{MPLTEXT 1 0 26 " while n>0 and k+j0 do x:= mult(x,x); k:=k-1; od;\n" }{MPLTEXT 1 0 15 " n:=n-1;\n" }{MPLTEXT 1 0 9 " fi;\n" }{MPLTEXT 1 0 7 " od;\n" }{MPLTEXT 1 0 20 " x:=mu lt(x,P[i]);\n" }{MPLTEXT 1 0 42 " while k>0 do x:=mult(x,x); k:=k-1; \+ od;\n" }{MPLTEXT 1 0 8 "od; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6& I\"aG6\"'I\"eGF%I'posintG%*protectedG'I\"mGF%F('I%multGF%I*procedureGF )6*I\"iGF%I\"jGF%I\"kGF%I\"PGF%I\"xGF%I\"bGF%I#aaGF%I\"nGF%F%F%C)>F5-I (convertGF)6%F'I%baseGF%\"\"#>F7,&-I%nopsGF)6#F5\"\"\"FD!\"\">F4F$>F37 #F$>F6-F-6$F$F$?(F1F>FD)F>,&F+FDFDFEI%trueGF)>F37$-I#opGF)6#F3-F-6$&F3 6#-FBFTF6?(F%FDFDF%FOC,@$/F7\"\"!OF4@$/&F56#F7FhnC%>F4-F-6$F4F4>F7,&F7 FDFDFE\\>F0FD>F1FD>F2FhnF_oFbo?(F%FDFDF%32FhnF72,&F2FDF1FDF+@%F[oC$>F2 ,&F2FDFDFDFboC'F_p>F1F\\p>F0*&F0FD)F>F2FD?(F%FDFDF%2FhnF2C$F_o>F2,&F2F DFDFEFbo>F4-F-6$F4&F36#F0FfpF%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "debug(fastexp); fastexp(2,11,1,(x,y)->x*y);" }}{PARA 11 "" 1 "" {XPPMATH 20 "I(fastexpG6\"" }}{PARA 9 "" 1 "" {TEXT 209 87 "\{--> enter fastexp, args = 2, 11, 1, proc (x, y) options operator, a rrow; x*y end proc" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"\"\"F#\"\"!F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "7#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#K" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" } }{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"%C5" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"%[?" }}{PARA 9 "" 1 "" {TEXT 209 44 "<-- exit fastexp ( now at top level) = 2048\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"%[?" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "debug(fastexp); fastexp(2,11 ,2,(x,y)->x*y);" }}{PARA 11 "" 1 "" {XPPMATH 20 "I(fastexpG6\"" }} {PARA 9 "" 1 "" {TEXT 209 87 "\{--> enter fastexp, args = 2, 11, 2, pr oc (x, y) options operator, arrow; x*y end proc" }}{PARA 11 "" 1 "" {XPPMATH 20 "7&\"\"\"F#\"\"!F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "7#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "7$\"\"#\"\")" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"%" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#;" }}{PARA 11 " " 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$c#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"%[?" }}{PARA 9 "" 1 "" {TEXT 209 44 "<-- exit f astexp (now at top level) = 2048\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "\" %[?" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 14 "2.16. Feladat." }}} {SECT 0 {PARA 4 "" 0 "" {TEXT 206 19 "2.17. Pollard p-1 m" }{TEXT 206 8 "\303\263" }{TEXT 206 7 "dszere." }}{PARA 0 "" 0 "" {TEXT 201 0 "" } }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 46 "# Thi s procedure is Pollard's p-1 method for\n" }{MPLTEXT 1 0 47 "# factori zation. The base is a, and powers of\n" }{MPLTEXT 1 0 46 "# primes up \+ to P are considered so that they\n" }{MPLTEXT 1 0 34 "# are not less t hen the bound B.\n" }{MPLTEXT 1 0 48 "# The result is the power x of a mod n, where\n" }{MPLTEXT 1 0 61 "# n isthe number to factorize, so \+ the factor is gcd(x-1,n).\n" }{MPLTEXT 1 0 3 "#\n" }{MPLTEXT 1 0 2 "\n " }{MPLTEXT 1 0 45 "pollardpsplit:=proc(n,a,B,P) local e,d,p,x;\n" } {MPLTEXT 1 0 13 "x:=a mod n;\n" }{MPLTEXT 1 0 44 "if igcd(x-1,n)>1 or \+ P<2 then return(x) fi;\n" }{MPLTEXT 1 0 27 "if P<2 then return(x) fi; \n" }{MPLTEXT 1 0 33 "e:=1; while 2^e1 or P=2 \+ then return(x) fi;\n" }{MPLTEXT 1 0 37 "while 3^e>3*B and e>1 do e:=e- 1 od;\n" }{MPLTEXT 1 0 20 "x:=x&^(3^e) mod n;\n" }{MPLTEXT 1 0 13 "d:= 2; p:=5;\n" }{MPLTEXT 1 0 15 "while true do\n" }{MPLTEXT 1 0 46 " if \+ igcd(x-1,n)>1 or P

p*B and e>1 do e:=e-1 od;\n" }{MPLTEXT 1 0 22 " x:=x&^(p^e) mod n; \n" }{MPLTEXT 1 0 19 " p:=p+d; d:=6-d;\n" }{MPLTEXT 1 0 11 "od; x; en d;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6&I\"nG6\"I\"aGF%I\"BGF%I\"PGF%6 &I\"eGF%I\"dGF%I\"pGF%I\"xGF%F%F%C/>F--I$modGF%6$F&F$@$52\"\"\"-I%igcd G%*protectedG6$,&F-F6F6!\"\"F$2F(\"\"#OF-@$F=F?>F*F6?(F%F6F6F%2)F>F*F' >F*,&F*F6F6F6>F--F16$-I#&^GF%6$F-FDF$@$5F5/F(F>F??(F%F6F6F%32,$*&\"\"$ F6F'F6F6)FUF*2F6F*>F*,&F*F6F6F<>F--F16$-FK6$F-FVF$>F+F>>F,\"\"&?(F%F6F 6F%I%trueGF9C'@$5F52F(F,F??(F%F6F6F%32*&F,F6F'F6)F,F*FWFX>F--F16$-FK6$ F-FfoF$>F,,&F,F6F+F6>F+,&\"\"'F6F+F " 0 "" {MPLTEXT 1 0 31 "pollardpsplit(25852,2,100,100);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"&CL#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "i gcd(%-1,25852);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$\"G" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "pollardpsplit(999863*999917*999961, 23,2000,1000);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"2:jYQ.\"HD;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "igcd(%-1,999863*999917*99996 1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'<****" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 14 "2.18. Feladat." }}}{SECT 0 {PARA 4 "" 0 "" {TEXT 206 19 "2.19. Pollard p-1 m" }{TEXT 206 8 "\303\263" }{TEXT 206 9 "dsz ere, m" }{TEXT 206 8 "\303\241" }{TEXT 206 7 "sodik l" }{TEXT 206 8 " \303\251" }{TEXT 206 3 "pcs" }{TEXT 206 9 "\305\221." }}{PARA 0 "" 0 " " {TEXT 201 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "#\n" } {MPLTEXT 1 0 65 "# This procedure is the second step of Pollard's p-1 \+ method for\n" }{MPLTEXT 1 0 56 "# factorization. The base is a, and pr imes from list P\n" }{MPLTEXT 1 0 64 "# are considered. The result is \+ the power x of a mod n, where\n" }{MPLTEXT 1 0 62 "# n is the number \+ to factorize, so the factor is gcd(x-1,n).\n" }{MPLTEXT 1 0 3 "#\n" } {MPLTEXT 1 0 2 "\n" }{MPLTEXT 1 0 73 "pollardp2split:=proc(n::posint,a ::posint,N::posint,m::posint,M::posint)\n" }{MPLTEXT 1 0 26 "local x,i ,j,E,aa,p,pp,d;\n" }{MPLTEXT 1 0 42 "E:=Array(1..N); aa:=a*a mod n; E[ 1]:=aa;\n" }{MPLTEXT 1 0 42 "for j from 2 to N do E[j]:=E[j-1]*aa od; \n" }{MPLTEXT 1 0 32 "p:=ithprime(m); x:=a&^p mod n;\n" }{MPLTEXT 1 0 43 "for i from m+1 to M while gcd(x-1,n)=1 do\n" }{MPLTEXT 1 0 37 " p p:=nextprime(p); d:=pp-p; p:=pp;\n" }{MPLTEXT 1 0 37 " if d<=2*N then x:=x*E[d/2] mod n;\n" }{MPLTEXT 1 0 31 " else x:=x*(a&^d) mod n; fi; \n" }{MPLTEXT 1 0 11 "od; x; end;" }}{PARA 11 "" 1 "" {XPPMATH 20 "f*6 ''I\"nG6\"I'posintG%*protectedG'I\"aGF&F''I\"NGF&F''I\"mGF&F''I\"MGF&F '6*I\"xGF&I\"iGF&I\"jGF&I\"EGF&I#aaGF&I\"pGF&I#ppGF&I\"dGF&F&F&C*>F5-I &ArrayGF(6#;\"\"\"F,>F6-I$modGF&6$*&F*F@F*F@F%>&F56#F@F6?(F4\"\"#F@F,I %trueGF(>&F56#F4*&&F56#,&F4F@F@!\"\"F@F6F@>F7-I)ithprimeGF&6#F.>F2-FC6 $-I#&^GF&6$F*F7F%?(F3,&F.F@F@F@F@F0/-I$gcdGF&6$,&F2F@F@FSF%F@C&>F8-I*n extprimeGF&6#F7>F9,&F8F@F7FS>F7F8@%1F9,$*&FJF@F,F@F@>F2-FC6$*&F2F@&F56 #,$*&#F@FJF@F9F@F@F@F%>F2-FC6$*&F2F@-Ffn6$F*F9F@F%F2F&F&F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "pollardpsplit(8174912477117*2352856 9104401,3,1000,1000);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\" " 0 "" {MPLTEXT 1 0 39 "igcd(%-1,81749124771 17*23528569104401);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 62 "pollardp2split(8174912477117 *23528569104401,%%,100,100,10000);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\" :mYD\"f.W>>M`9R" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "igcd(%-1 ,8174912477117*23528569104401);" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"/,W 5p&GN#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "ifactor(%-1);" }} {PARA 11 "" 1 "" {XPPMATH 20 "*.)-I!G6\"6#\"\"#\"\"%\"\"\")-F%6#\"\"&F (F*-F%6#\"#nF*-F%6#\"$2\"F*-F%6#\"$*>F*-F%6#\"&J7%F*" }}}}{SECT 1 {PARA 4 "" 0 "" {TEXT 206 14 "2.20. Feladat." }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 64 "3. Egyszer\305\261 pr\303\255mtesztel\303\251si m\30 3\263dszerek" }}{EXCHG {PARA 0 "" 0 "" {XPPEDIT 2 0 "" "%#%?G" }}}} {SECT 1 {PARA 3 "" 0 "" {TEXT 205 18 "4. Lucas-sorozatok" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 23 "5. Alkal maz\303\241sok " }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 " " 0 "" {TEXT 205 36 "6. Sz\303\241mok \303\251s polinomok" }}{PARA 0 " " 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 45 "7. Gyor s Fourier-transzform\303\241ci\303\263" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 38 "8. Elliptikus f\303\274ggv \303\251nyek" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 59 "9. Sz\303\241mol\303\241s elliptikus g\303\266rb\303 \251ken" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 65 "10. Faktoriz\303\241l\303\241s elliptikus g\303\266rb\30 3\251kkel" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 55 "11. Pr\303\255mteszt elliptikus g\303\266rb\303\251kkel " }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 37 "12. Polinomfaktoriz\303\241l\303\241s" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 16 "13. Az AKS-teszt" } }}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 36 "14. A szita m\303\263dszerek a lapjai" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 25 "15. Sz\303\241mtest szita" }}{PARA 0 "" 0 "" {TEXT 201 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT 205 16 "16. Vegyes probl" }{TEXT 205 8 "\303\251" }{TEXT 205 1 "m" }{TEXT 205 8 "\303\241" }{TEXT 205 1 "k" }}}{EXCHG {PARA 205 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 201 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {XPPEDIT 19 1 "" "%#%?G" }}}} {MARK "0 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }