Category : BASIC Source Code
Archive   : UBAS830.ZIP
Filename : LLL.UB

O
˜This program impliments the reduction algorithm of Lengstra, Lengstra,
ž˜and Lovasz (Math. Ann. 261 (1982) 515-534) to obtain a "reduced basis"
ç˜for a positive definite real valued bilinear form A(-,-) on Z^n.
3
˜I have added a search algorithm to find short vectors for the form.
<
˜
…
˜The parameter PP should be between .25 and 1. The routine seems
®
˜fairly insensitive to its value.
Ô
˜ Written by W.D. Neumann
ã

Ÿñ À©ñ
ñ
NÑñ(
V¤„ANN)„BNN)„CNN)„MNN)„VN)˜used by main algorithm
”(¤„XN)„YN)„ZN)˜A used by *SEARCH
¤2ƒPPÑð.ñ
­<˜œ
æF˜ Set up a form to play with to test the routine.
ïG˜
INÑñÀƒXрÅñ)݀Åñ)Þñ
]J‰ƒIÑðŠNÀ‰ƒJÑðŠNÀ„AƒIƒJ)ÑñïñåƒXï(ƒI݃J)ÀŒ
†K„AƒIƒI)фAƒIƒI)Ýñ
ÀŒ
P˜
ÙQ˜ The minimal polynomial for X gives a short vector for this form.
âR˜
ñSˆõMAINó
Tˆõ PRINTFORMðóˆõ PRINTBASE
ôˆõPRINTINVÕó
5UˆõSEARCH¹ó‡ñU
>d˜
†n˜ Subroutine to compute the A-inner product of d(n,-) and d(m,-)
Éx˜ A() must be initialized to the definite form in question.
Ò‚˜
ïŒõIP(&„DƒNƒM)
ÿºƒIƒJ
Ž¨ƒIP
d–‰ƒIÑðŠNÀ‰ƒJÑðŠNÀƒIPуIP݄AƒIƒJ)å„DƒNƒI)å„DƒMƒJ)ÀŒÀŒ
k •
tȘ
‚ÒõMAIN
‹Ü˜I
×æ˜ At any time during the reduction, B(i,-) is the ith basis element.
ð˜ So BABt is the matrix of the form with respect to the B-basis.
Dú˜ (Bt means transpose of B.)

˜ We start with the standard basis, though this is not essential.
–
˜
Ö
¨¢„BðÁNÂðÁN)À‰ƒIÑðŠNÀ„BƒIƒI)Ññ
ÀŒƒI
ß"
˜«
%,
˜ M will be a lower triangular matrix with 1's on the diagonal
i6
˜ (its entries below the diagonal are M(i,j)). We do a Gram
µ@
˜ reduction to find C and M such that B=MC and CACt=Diag(V1,...,Vn).
õJ
˜ In particular, (A =) BABt = MVMt, where V is diagonal.
þT
˜
!^
™"Initializing reduction..."Á
Nh
¢„CðÁNÂðÁN)Ñ¢„BðÁNÂðÁN)
`r
‰ƒIÑðŠN
v|
‰ƒJÑðŠƒIÞñ

²†
ˆõIPËò(&„CƒIƒJ)À„MƒIƒJ)уIPæ„VƒJ)
 
‰ƒKÑðŠNÀ„CƒIƒK)фCƒIƒK)ބMƒIƒJ)å„CƒJƒK)ÀŒƒK
 š
ŒƒJ
> ¤
ˆõIPËò(&„CƒIƒI)À„VƒI)уIP
I ®
ŒƒI
R ¸
˜ú
– Â
˜ We re-use C(-,-) to hold B^-1 (actually (old B)*(new B)^-1
Ú Ì
˜ for any initial choice of B). B^-1 is not needed for most
#
Ö
˜ applications, so the code to compute it can usually be deleted.
D
à
˜ We first initialize it.
M
ê
˜

ô
¨¢„CðÁNÂðÁN)À‰ƒIÑðŠNÀ„CƒIƒI)Ññ
ÀŒƒI
–
þ
˜c
ß
˜ The main reduction algorithm follows. It operates on the basis
%˜ B so that after reduction we have new B,M,V still satisfying
i˜ BABt=MVMt, but with all Mij <= .5 and with a constraint on
­&˜ the entries of V (which implies V(k) >= V(k-1)*(PP-.25) ).
¶0˜
Ñ:™"STARTING REDUCTION"
çDƒKÑñ
À‡õR1£
\ NõR2ƒMфMƒKƒKÞñ
)ÀƒVфVƒK)݃MåƒMå„VƒKÞñ
)À„MƒKƒKÞñ
)уMå„VƒKÞñ
)æƒV
› X„VƒK)фVƒKÞñ
)å„VƒK)æƒVÀ„VƒKÞñ
)уV
É b¥¢„BƒKÂðÁN)¢„BƒKÞñ
ÂðÁN)
÷ c¥¢„CðÁNƒK)¢„CðÁNƒKÞñ
)
9
læƒKÒñ
Ž¥¢„MƒKÂðÃKÞñ)¢„MƒKÞñ
ÂðÃKÞñ)
R
v‰ƒIуKÝñ
ŠN
Ó
€ƒVфMƒIƒK)À„MƒIƒK)фMƒIƒKÞñ
)ރMåƒVÀ„MƒIƒKÞñ
)уV݄MƒKƒKÞñ
)å„MƒIƒK)ÀŒ
ê
Š—ƒKÒñ
Ž¡ƒK
”õR1ƒLуKÞñ
ÀˆõR3ó
]ž
„VƒK)æ„VƒKÞñ
)݄MƒKƒKÞñ
)å„MƒKƒKÞñ
)ԃPP‡õR2 
…¨‰ƒLуKÞñŠð‹Þñ
ÀˆõR3óŒƒL
¤² ƒKÀQƒKՁN‡õR1£
ͼ•˜ -------------------->
õÆõR3¢€À„MƒKƒL))Õð.ñŽ•
ЃRрÜð.ñ݄MƒKƒL))
“Ú‰ƒIÑðŠNÀ„BƒKƒI)фBƒKƒI)ރRå„BƒLƒI)À„CƒIƒL)фCƒIƒL)݃Rå„CƒIƒK)ÀŒƒI
ä„MƒKƒL)фMƒKƒL)ރRÀ‰ƒIÑðŠƒLÞñ
À„MƒKƒI)фMƒKƒI)ރRå„MƒLƒI)ÀŒ
î•
ø˜
X˜ The following routine uses the normal form to search for ALL
¢ ˜ vectors up to a given squared length with respect to the form.
Ò˜ It only list one of each pair w, -w.
Û ˜
*õSEARCHƒKсNÀ¨„YN)„ZN)ƒNN
U4§"Search up to square length (try v(0) for shortest vector)"ÁƒTT
•>§"Print vectors (0/1)"ÁSSÀSSŽ™"vector | square len"
¢H‡õS1
RõS0¡ƒKÀ„ZƒK)ÑðÀ‰ƒIуKÝñ
ŠNÀ„ZƒK)фZƒK)݄MƒIƒK)å„XƒI)ÀŒ
O\„YƒK)фYƒKÝñ
)݄VƒKÝñ
)å(„XƒKÝñ
)݄ZƒKÝñ
))ïñ
fõS1„XƒK)р܀Å(ƒTTބYƒK))æ„VƒK))ބZƒK))
åpõS2„VƒK)å(„XƒK)݄ZƒK))ïñ҃TTބYƒK)À ƒKÀ¡„XƒK)À‘
z˜if K=N%+1 then print "ERROR":stop:return
*„ƒK‡õS0[
rŽ€è„Xð)„Yð)}Þñ
Ž™ñåƒNNÁ"nonzero vectors up to"ÁƒTTÀ•
“˜SSŽ‰ƒIÑðŠNÀƒACÑð
Û™À‰ƒJÑðŠNÀƒACуAC݄XƒJ)å„BƒJƒI)ÀŒÀ™€ìñ)ƒACÁÀŒ
šÀ™€âñ<)Á"|"ÁÀƒPRфVð)å(„Xð)݄Zð))ïñ݄Yð)ÀˆõPRó™
<¢ ƒNNÀ¡„XƒK)À‡õS2H
E¬˜
z¶õ PRINTFORM™"Form with respect to new basis:"
ÆÀ‰ƒIÑðŠNÀ‰ƒJÑðŠNÀs!ƒJԃIŽƒPRфMƒJƒI)ÀˆõPRó‡ñÔ
ʈõIPËò(&„BƒIƒJ)À„MƒIƒJ)уIPÀƒPRуIPÀˆõPRó
ÔŒÀ™ÀŒÀ•
HÞõ PRINTLENGTHS™"Lengths of basis vectors"
Šß‰ƒIÑðŠNÀˆõIP(&„BƒIƒI)ÀƒPRуIPÀˆõPRŒÀ™À•
²èõ PRINTBASE™"Basis"À‰ƒIÑðŠN
ä鉃JÑðŠNÀ™€ìñ)„BƒIƒJ)ÁÀŒÀ™ÀŒÀ•
òõPRINTINV™"Inverse of basis matrix"
Hó‰ƒIÑðŠNÀ‰ƒJÑðŠNÀ™„CƒIƒJ)ÁÀŒÀ™ÀŒÀ•
QИ
qÖõPRƒPEÑðÀ#ƒPRÑðŽ¶
¥àR#€ÀƒPR)Óñ
ÀƒPRуPRæñ
ÀƒPEуPEÝñ
À‘%#
Ùꐆ#€ÀƒPR)Ôñ
ÀƒPRуPRåñ
ÀƒPEуPEÞñ
À‘Y#
ô·À™€ìñÂñ)ƒPRÁ" E"Á€ìñ)ƒPEÁ
þ•