Summary. In RSA Cryptograms, many modulo calculations are used, but modulo calculation is based on many subtractions and it takes long time to calculate. In this article, we explain about a new modulo calculation algorithm using table. And we proof that up
JOURNALOFFORMALIZEDMATHEMATICS
Volume15,Released2003,Published2003
Inst.ofComputerScience,Univ.ofBia ystok
HighSpeedModuloCalculationAlgorithmwith
Radix-2kSDNumber
MasaakiNiimura
ShinshuUniversity
NaganoYasushiFuwaShinshuUniversityNagano
Summary.InRSACryptograms,manymodulocalculationsareused,butmodulo
calculationisbasedonmanysubtractionsandittakeslongtimetocalculate.Inthisarticle,
weexplainaboutanewmodulocalculationalgorithmusingtable.Andweproofthatupper
3digitsofRadix-2kSDnumbersisenoughtospecifytheanswer.Inthe rstsection,we
preparedsomeusefultheoremsforoperationsofRadix-2kSDNumber.Inthesecondsection,
wede nedUpper3DigitsofRadix-2kSDnumberandprovedthatproperty.Inthethird
section,weprovedsomepropertyabouttheminimumdigitsofRadix-2kSDnumber.Inthe
fourthsection,weidenti edtherangeofmoduloarithmeticresultandprovedthattheUpper
3Digitsindicatetwopossibleanswers.Andinthelastsection,wede nedafunctiontoselect
trueanswerfromtheresultsofUpper3Digits.
MMLIdenti er:RADIX_6.WWW:doc.guandang.net[8],[10],[9],[1],[7],[4],[2],[3],[11],[5],and[6]providethenotationandterminol-ogyforthispaper.
1.SOMEUSEFULTHEOREMS
Thefollowingtwopropositionsaretrue:
(1)Letnbeanaturalnumber.Supposen≥1.Letm,kbenaturalnumbers.Ifm≥1andk≥2,
thenSDDecFmin(m+n,m,k)=SDDecFmin(m,m,k).
(2)
2.Forallnaturalnumbersm,ksuchthatm≥1andk≥2holdsSDDecFmin(m,m,k)>0.DEFINITIONSOFUPPER3DIGITSOFRADIX-2kSDNUMBERANDITSPROPERTY
Leti,m,kbenaturalnumbersandletrbeam+2-tupleofk SD.Letusassumethati∈Seg(m+2).ThefunctorM0Digit(r,i)yieldsanelementofk SDandisde nedasfollows:
(Def.1)(i)
(ii)M0Digit(r,i)=r(i)ifi≥m,M0Digit(r,i)=0ifi<m.
Letm,kbenaturalnumbersandletrbeam+2-tupleofk SD.ThefunctorM0(r)yieldinga
m+2-tupleofk SDisde nedby:
(Def.2)Foreverynaturalnumberisuchthati∈Seg(m+2)holdsDigA(M0(r),i)=M0Digit(r,i).
1cAssociationofMizarUsers
high speed calculation method with Radix-2k ...For every natural number k holds k ?SD Sub S...2k signed-digit number and its adder algorithm. ...
One is ’bit compare’ at carry calculation, it...number k such that 3 k holds SDSubAddCarry(SD...high speed adder algorithm with radix-2k . . ....
High Speed Modulo Calcul... 暂无评价 4页 免费 Definitions of Radix-2 k...De?nitions of radix-2k signed-digit number and its adder algorithm. ...
High Speed Adder Algorit... 暂无评价 3页 免费 High Speed Modulo Calcul.... Definitions of Radix-2 k Signed-Digit Number and its Adder Algorithm ...
High-Speed and Low-Power... 暂无评价 11页 免费 High Speed Modulo ...For example, radix-24 algorithm has the same number of multipliers as the...
High Speed Modulo Calcul... 暂无评价 4页 免费 Asymmetric high-radix si....Takagi presented a radix-4 modular multiplication hardware algorithm suitable ...
For a radix-2 FFT calculation, a number of ...Modulo N reduction is necessary for these index ...“A Prime Factor FFT Algorithm Using Highspeed ...
For a radix-2 FFT calculation, a number of ...Modulo N reduction is necessary for these index ...“A Prime Factor FFT Algorithm Using Highspeed ...
热门文档