Open ebfull opened 6 years ago
Just wanted to add these two as a baseline: Fq 306 operations: https://gist.github.com/ValarDragon/4bdc17282323e3744106cf812ee08875 Fr 303 operations: https://gist.github.com/ValarDragon/623dfffd758373b8059ddd17c8344b99
chains obtained using https://github.com/kwantam/addchain
Thanks @ValarDragon!
For reference: https://github.com/Eirik0/add-chain-converter
https://github.com/zkcrypto/jubjub/pull/12 implemented the addition chain referenced above for Fr.
Addition chain for t
for Jubjub Fq
:
$ go run *.go 12208678567578594777604504606729831043093128246378069236549469339647
# Bos-Coster (win=4) : 272 (14)
# Bos-Coster (win=5) : 269 (17)
# Bos-Coster (win=7) : 269 (18)
# Bos-Coster (win=10) : 277 (18)
# Bos-Coster (win=8) : 273 (21)
# Bos-Coster (win=3) : 274 ( 9)
# Bos-Coster (win=6) : 272 (20)
# Bos-Coster (win=2) : 281 ( 5)
# Yacobi : 286 (23)
# Bergeron-Berstel-Brlek-Duboc : 287 ( 4)
# Bos-Coster (win=9) : 284 (20)
t13 = input # 0 : 1
t1 = sqr(t13) # 1 : 2
t3 = sqr(t1) # 2 : 4
t2 = t3 * t1 # 3 : 6
t4 = sqr(t2) # 4 : 12
t0 = t4 * t2 # 5 : 18
t12 = t0 * t13 # 6 : 19
t9 = t12 * t1 # 7 : 21
t10 = t9 * t2 # 8 : 27
t16 = t10 * t1 # 9 : 29
t1 = t12 * t4 # 10 : 31
t11 = t9 * t4 # 11 : 33
t8 = t9 * t0 # 12 : 39
t6 = t16 * t4 # 13 : 41
t4 = t10 * t0 # 14 : 45
t5 = t16 * t0 # 15 : 47
t15 = t11 * t0 # 16 : 51
t3 = t15 * t3 # 17 : 55
t14 = t8 * t0 # 18 : 57
t7 = t3 * t2 # 19 : 61
t2 = t4 * t0 # 20 : 63
t0 = sqr(t14) # 21 : 114
t0 = sqr(t0) # 22 : 228
t0 = sqr(t0) # 23 : 456
t0 = sqr(t0) # 24 : 912
t0 = sqr(t0) # 25 : 1824
t0 = sqr(t0) # 26 : 3648
t0 = t0 * t7 # 27 : 3709
t0 = sqr(t0) # 28 : 7418
t0 = sqr(t0) # 29 : 14836
t0 = sqr(t0) # 30 : 29672
t0 = sqr(t0) # 31 : 59344
t0 = sqr(t0) # 32 : 118688
t0 = sqr(t0) # 33 : 237376
t0 = t0 * t4 # 34 : 237421
t0 = sqr(t0) # 35 : 474842
t0 = sqr(t0) # 36 : 949684
t0 = sqr(t0) # 37 : 1899368
t0 = sqr(t0) # 38 : 3798736
t0 = sqr(t0) # 39 : 7597472
t0 = sqr(t0) # 40 : 15194944
t0 = sqr(t0) # 41 : 30389888
t0 = t0 * t16 # 42 : 30389917
t0 = sqr(t0) # 43 : 60779834
t0 = sqr(t0) # 44 : 121559668
t0 = sqr(t0) # 45 : 243119336
t0 = sqr(t0) # 46 : 486238672
t0 = sqr(t0) # 47 : 972477344
t0 = sqr(t0) # 48 : 1944954688
t0 = t0 * t12 # 49 : 1944954707
t0 = sqr(t0) # 50 : 3889909414
t0 = sqr(t0) # 51 : 7779818828
t0 = sqr(t0) # 52 : 15559637656
t0 = sqr(t0) # 53 : 31119275312
t0 = sqr(t0) # 54 : 62238550624
t0 = sqr(t0) # 55 : 124477101248
t0 = sqr(t0) # 56 : 248954202496
t0 = sqr(t0) # 57 : 497908404992
t0 = t0 * t6 # 58 : 497908405033
t0 = sqr(t0) # 59 : 995816810066
t0 = sqr(t0) # 60 : 1991633620132
t0 = sqr(t0) # 61 : 3983267240264
t0 = sqr(t0) # 62 : 7966534480528
t0 = sqr(t0) # 63 : 15933068961056
t0 = sqr(t0) # 64 : 31866137922112
t0 = t0 * t8 # 65 : 31866137922151
t0 = sqr(t0) # 66 : 63732275844302
t0 = sqr(t0) # 67 : 127464551688604
t0 = sqr(t0) # 68 : 254929103377208
t0 = sqr(t0) # 69 : 509858206754416
t0 = sqr(t0) # 70 : 1019716413508832
t0 = sqr(t0) # 71 : 2039432827017664
t0 = sqr(t0) # 72 : 4078865654035328
t0 = t0 * t5 # 73 : 4078865654035375
t0 = sqr(t0) # 74 : 8157731308070750
t0 = sqr(t0) # 75 : 16315462616141500
t0 = sqr(t0) # 76 : 32630925232283000
t0 = sqr(t0) # 77 : 65261850464566000
t0 = sqr(t0) # 78 : 130523700929132000
t0 = t0 * t9 # 79 : 130523700929132021
t0 = sqr(t0) # 80 : 261047401858264042
t0 = sqr(t0) # 81 : 522094803716528084
t0 = sqr(t0) # 82 : 1044189607433056168
t0 = t0 * t13 # 83 : 1044189607433056169
t0 = sqr(t0) # 84 : 2088379214866112338
t0 = sqr(t0) # 85 : 4176758429732224676
t0 = sqr(t0) # 86 : 8353516859464449352
t0 = sqr(t0) # 87 : 16707033718928898704
t0 = sqr(t0) # 88 : 33414067437857797408
t0 = sqr(t0) # 89 : 66828134875715594816
t0 = sqr(t0) # 90 : 133656269751431189632
t0 = sqr(t0) # 91 : 267312539502862379264
t0 = sqr(t0) # 92 : 534625079005724758528
t0 = sqr(t0) # 93 : 1069250158011449517056
t0 = sqr(t0) # 94 : 2138500316022899034112
t0 = t0 * t15 # 95 : 2138500316022899034163
t0 = sqr(t0) # 96 : 4277000632045798068326
t0 = sqr(t0) # 97 : 8554001264091596136652
t0 = sqr(t0) # 98 : 17108002528183192273304
t0 = sqr(t0) # 99 : 34216005056366384546608
t0 = sqr(t0) # 100 : 68432010112732769093216
t0 = sqr(t0) # 101 : 136864020225465538186432
t0 = sqr(t0) # 102 : 273728040450931076372864
t0 = sqr(t0) # 103 : 547456080901862152745728
t0 = t0 * t14 # 104 : 547456080901862152745785
t0 = sqr(t0) # 105 : 1094912161803724305491570
t0 = sqr(t0) # 106 : 2189824323607448610983140
t0 = sqr(t0) # 107 : 4379648647214897221966280
t0 = sqr(t0) # 108 : 8759297294429794443932560
t0 = sqr(t0) # 109 : 17518594588859588887865120
t0 = t0 * t10 # 110 : 17518594588859588887865147
t0 = sqr(t0) # 111 : 35037189177719177775730294
t0 = sqr(t0) # 112 : 70074378355438355551460588
t0 = sqr(t0) # 113 : 140148756710876711102921176
t0 = sqr(t0) # 114 : 280297513421753422205842352
t0 = sqr(t0) # 115 : 560595026843506844411684704
t0 = sqr(t0) # 116 : 1121190053687013688823369408
t0 = sqr(t0) # 117 : 2242380107374027377646738816
t0 = sqr(t0) # 118 : 4484760214748054755293477632
t0 = t0 * t13 # 119 : 4484760214748054755293477633
t0 = sqr(t0) # 120 : 8969520429496109510586955266
t0 = sqr(t0) # 121 : 17939040858992219021173910532
t0 = sqr(t0) # 122 : 35878081717984438042347821064
t0 = sqr(t0) # 123 : 71756163435968876084695642128
t0 = sqr(t0) # 124 : 143512326871937752169391284256
t0 = sqr(t0) # 125 : 287024653743875504338782568512
t0 = sqr(t0) # 126 : 574049307487751008677565137024
t0 = sqr(t0) # 127 : 1148098614975502017355130274048
t0 = sqr(t0) # 128 : 2296197229951004034710260548096
t0 = sqr(t0) # 129 : 4592394459902008069420521096192
t0 = sqr(t0) # 130 : 9184788919804016138841042192384
t0 = sqr(t0) # 131 : 18369577839608032277682084384768
t0 = t0 * t12 # 132 : 18369577839608032277682084384787
t0 = sqr(t0) # 133 : 36739155679216064555364168769574
t0 = sqr(t0) # 134 : 73478311358432129110728337539148
t0 = sqr(t0) # 135 : 146956622716864258221456675078296
t0 = sqr(t0) # 136 : 293913245433728516442913350156592
t0 = sqr(t0) # 137 : 587826490867457032885826700313184
t0 = sqr(t0) # 138 : 1175652981734914065771653400626368
t0 = sqr(t0) # 139 : 2351305963469828131543306801252736
t0 = t0 * t11 # 140 : 2351305963469828131543306801252769
t0 = sqr(t0) # 141 : 4702611926939656263086613602505538
t0 = sqr(t0) # 142 : 9405223853879312526173227205011076
t0 = sqr(t0) # 143 : 18810447707758625052346454410022152
t0 = sqr(t0) # 144 : 37620895415517250104692908820044304
t0 = sqr(t0) # 145 : 75241790831034500209385817640088608
t0 = t0 * t10 # 146 : 75241790831034500209385817640088635
t0 = sqr(t0) # 147 : 150483581662069000418771635280177270
t0 = sqr(t0) # 148 : 300967163324138000837543270560354540
t0 = sqr(t0) # 149 : 601934326648276001675086541120709080
t0 = sqr(t0) # 150 : 1203868653296552003350173082241418160
t0 = sqr(t0) # 151 : 2407737306593104006700346164482836320
t0 = sqr(t0) # 152 : 4815474613186208013400692328965672640
t0 = sqr(t0) # 153 : 9630949226372416026801384657931345280
t0 = sqr(t0) # 154 : 19261898452744832053602769315862690560
t0 = sqr(t0) # 155 : 38523796905489664107205538631725381120
t0 = sqr(t0) # 156 : 77047593810979328214411077263450762240
t0 = sqr(t0) # 157 : 154095187621958656428822154526901524480
t0 = sqr(t0) # 158 : 308190375243917312857644309053803048960
t0 = sqr(t0) # 159 : 616380750487834625715288618107606097920
t0 = t0 * t9 # 160 : 616380750487834625715288618107606097941
t0 = sqr(t0) # 161 : 1232761500975669251430577236215212195882
t0 = sqr(t0) # 162 : 2465523001951338502861154472430424391764
t0 = sqr(t0) # 163 : 4931046003902677005722308944860848783528
t0 = sqr(t0) # 164 : 9862092007805354011444617889721697567056
t0 = sqr(t0) # 165 : 19724184015610708022889235779443395134112
t0 = sqr(t0) # 166 : 39448368031221416045778471558886790268224
t0 = sqr(t0) # 167 : 78896736062442832091556943117773580536448
t0 = t0 * t8 # 168 : 78896736062442832091556943117773580536487
t0 = sqr(t0) # 169 : 157793472124885664183113886235547161072974
t0 = sqr(t0) # 170 : 315586944249771328366227772471094322145948
t0 = sqr(t0) # 171 : 631173888499542656732455544942188644291896
t0 = sqr(t0) # 172 : 1262347776999085313464911089884377288583792
t0 = sqr(t0) # 173 : 2524695553998170626929822179768754577167584
t0 = sqr(t0) # 174 : 5049391107996341253859644359537509154335168
t0 = sqr(t0) # 175 : 10098782215992682507719288719075018308670336
t0 = t0 * t7 # 176 : 10098782215992682507719288719075018308670397
t0 = sqr(t0) # 177 : 20197564431985365015438577438150036617340794
t0 = sqr(t0) # 178 : 40395128863970730030877154876300073234681588
t0 = sqr(t0) # 179 : 80790257727941460061754309752600146469363176
t0 = sqr(t0) # 180 : 161580515455882920123508619505200292938726352
t0 = sqr(t0) # 181 : 323161030911765840247017239010400585877452704
t0 = sqr(t0) # 182 : 646322061823531680494034478020801171754905408
t0 = t0 * t6 # 183 : 646322061823531680494034478020801171754905449
t0 = sqr(t0) # 184 : 1292644123647063360988068956041602343509810898
t0 = sqr(t0) # 185 : 2585288247294126721976137912083204687019621796
t0 = sqr(t0) # 186 : 5170576494588253443952275824166409374039243592
t0 = sqr(t0) # 187 : 10341152989176506887904551648332818748078487184
t0 = sqr(t0) # 188 : 20682305978353013775809103296665637496156974368
t0 = sqr(t0) # 189 : 41364611956706027551618206593331274992313948736
t0 = sqr(t0) # 190 : 82729223913412055103236413186662549984627897472
t0 = sqr(t0) # 191 : 165458447826824110206472826373325099969255794944
t0 = sqr(t0) # 192 : 330916895653648220412945652746650199938511589888
t0 = sqr(t0) # 193 : 661833791307296440825891305493300399877023179776
t0 = sqr(t0) # 194 : 1323667582614592881651782610986600799754046359552
t0 = sqr(t0) # 195 : 2647335165229185763303565221973201599508092719104
t0 = sqr(t0) # 196 : 5294670330458371526607130443946403199016185438208
t0 = sqr(t0) # 197 : 10589340660916743053214260887892806398032370876416
t0 = t0 * t5 # 198 : 10589340660916743053214260887892806398032370876463
t0 = sqr(t0) # 199 : 21178681321833486106428521775785612796064741752926
t0 = sqr(t0) # 200 : 42357362643666972212857043551571225592129483505852
t0 = sqr(t0) # 201 : 84714725287333944425714087103142451184258967011704
t0 = sqr(t0) # 202 : 169429450574667888851428174206284902368517934023408
t0 = sqr(t0) # 203 : 338858901149335777702856348412569804737035868046816
t0 = sqr(t0) # 204 : 677717802298671555405712696825139609474071736093632
t0 = t0 * t2 # 205 : 677717802298671555405712696825139609474071736093695
t0 = sqr(t0) # 206 : 1355435604597343110811425393650279218948143472187390
t0 = sqr(t0) # 207 : 2710871209194686221622850787300558437896286944374780
t0 = sqr(t0) # 208 : 5421742418389372443245701574601116875792573888749560
t0 = sqr(t0) # 209 : 10843484836778744886491403149202233751585147777499120
t0 = sqr(t0) # 210 : 21686969673557489772982806298404467503170295554998240
t0 = t0 * t1 # 211 : 21686969673557489772982806298404467503170295554998271
t0 = sqr(t0) # 212 : 43373939347114979545965612596808935006340591109996542
t0 = sqr(t0) # 213 : 86747878694229959091931225193617870012681182219993084
t0 = sqr(t0) # 214 : 173495757388459918183862450387235740025362364439986168
t0 = sqr(t0) # 215 : 346991514776919836367724900774471480050724728879972336
t0 = sqr(t0) # 216 : 693983029553839672735449801548942960101449457759944672
t0 = sqr(t0) # 217 : 1387966059107679345470899603097885920202898915519889344
t0 = sqr(t0) # 218 : 2775932118215358690941799206195771840405797831039778688
t0 = sqr(t0) # 219 : 5551864236430717381883598412391543680811595662079557376
t0 = t0 * t4 # 220 : 5551864236430717381883598412391543680811595662079557421
t0 = sqr(t0) # 221 : 11103728472861434763767196824783087361623191324159114842
t0 = sqr(t0) # 222 : 22207456945722869527534393649566174723246382648318229684
t0 = sqr(t0) # 223 : 44414913891445739055068787299132349446492765296636459368
t0 = sqr(t0) # 224 : 88829827782891478110137574598264698892985530593272918736
t0 = sqr(t0) # 225 : 177659655565782956220275149196529397785971061186545837472
t0 = sqr(t0) # 226 : 355319311131565912440550298393058795571942122373091674944
t0 = t0 * t2 # 227 : 355319311131565912440550298393058795571942122373091675007
t0 = sqr(t0) # 228 : 710638622263131824881100596786117591143884244746183350014
t0 = sqr(t0) # 229 : 1421277244526263649762201193572235182287768489492366700028
t0 = sqr(t0) # 230 : 2842554489052527299524402387144470364575536978984733400056
t0 = sqr(t0) # 231 : 5685108978105054599048804774288940729151073957969466800112
t0 = sqr(t0) # 232 : 11370217956210109198097609548577881458302147915938933600224
t0 = sqr(t0) # 233 : 22740435912420218396195219097155762916604295831877867200448
t0 = t0 * t3 # 234 : 22740435912420218396195219097155762916604295831877867200503
t0 = sqr(t0) # 235 : 45480871824840436792390438194311525833208591663755734401006
t0 = sqr(t0) # 236 : 90961743649680873584780876388623051666417183327511468802012
t0 = sqr(t0) # 237 : 181923487299361747169561752777246103332834366655022937604024
t0 = sqr(t0) # 238 : 363846974598723494339123505554492206665668733310045875208048
t0 = sqr(t0) # 239 : 727693949197446988678247011108984413331337466620091750416096
t0 = sqr(t0) # 240 : 1455387898394893977356494022217968826662674933240183500832192
t0 = t0 * t2 # 241 : 1455387898394893977356494022217968826662674933240183500832255
t0 = sqr(t0) # 242 : 2910775796789787954712988044435937653325349866480367001664510
t0 = sqr(t0) # 243 : 5821551593579575909425976088871875306650699732960734003329020
t0 = sqr(t0) # 244 : 11643103187159151818851952177743750613301399465921468006658040
t0 = sqr(t0) # 245 : 23286206374318303637703904355487501226602798931842936013316080
t0 = sqr(t0) # 246 : 46572412748636607275407808710975002453205597863685872026632160
t0 = sqr(t0) # 247 : 93144825497273214550815617421950004906411195727371744053264320
t0 = t0 * t2 # 248 : 93144825497273214550815617421950004906411195727371744053264383
t0 = sqr(t0) # 249 : 186289650994546429101631234843900009812822391454743488106528766
t0 = sqr(t0) # 250 : 372579301989092858203262469687800019625644782909486976213057532
t0 = sqr(t0) # 251 : 745158603978185716406524939375600039251289565818973952426115064
t0 = sqr(t0) # 252 : 1490317207956371432813049878751200078502579131637947904852230128
t0 = sqr(t0) # 253 : 2980634415912742865626099757502400157005158263275895809704460256
t0 = sqr(t0) # 254 : 5961268831825485731252199515004800314010316526551791619408920512
t0 = t0 * t2 # 255 : 5961268831825485731252199515004800314010316526551791619408920575
t0 = sqr(t0) # 256 : 11922537663650971462504399030009600628020633053103583238817841150
t0 = sqr(t0) # 257 : 23845075327301942925008798060019201256041266106207166477635682300
t0 = sqr(t0) # 258 : 47690150654603885850017596120038402512082532212414332955271364600
t0 = sqr(t0) # 259 : 95380301309207771700035192240076805024165064424828665910542729200
t0 = sqr(t0) # 260 : 190760602618415543400070384480153610048330128849657331821085458400
t0 = sqr(t0) # 261 : 381521205236831086800140768960307220096660257699314663642170916800
t0 = t0 * t2 # 262 : 381521205236831086800140768960307220096660257699314663642170916863
t0 = sqr(t0) # 263 : 763042410473662173600281537920614440193320515398629327284341833726
t0 = sqr(t0) # 264 : 1526084820947324347200563075841228880386641030797258654568683667452
t0 = sqr(t0) # 265 : 3052169641894648694401126151682457760773282061594517309137367334904
t0 = sqr(t0) # 266 : 6104339283789297388802252303364915521546564123189034618274734669808
t0 = sqr(t0) # 267 : 12208678567578594777604504606729831043093128246378069236549469339616
t0 = t0 * t1 # 268 : 12208678567578594777604504606729831043093128246378069236549469339647
# Bos-Coster (win=5) : 269 (17)
Addition chain for (t + 1)/2
for Jubjub Fq
:
$ go run *.go 6104339283789297388802252303364915521546564123189034618274734669824
# Bos-Coster (win=4) : 266 (15)
# Bos-Coster (win=2) : 269 ( 5)
# Bos-Coster (win=8) : 264 (17)
# Bos-Coster (win=6) : 267 (19)
# Bos-Coster (win=5) : 263 (17)
# Bos-Coster (win=10) : 272 (17)
# Bos-Coster (win=3) : 266 ( 9)
# Bos-Coster (win=7) : 264 (18)
# Bos-Coster (win=9) : 276 (18)
# Bergeron-Berstel-Brlek-Duboc : 288 ( 5)
# Yacobi : 275 (19)
t13 = input # 0 : 1
t0 = sqr(t13) # 1 : 2
t1 = sqr(t0) # 2 : 4
t0 = t1 * t0 # 3 : 6
t3 = sqr(t1) # 4 : 8
t4 = t3 * t0 # 5 : 14
t2 = t4 * t13 # 6 : 15
t12 = t2 * t1 # 7 : 19
t9 = t2 * t0 # 8 : 21
t10 = t12 * t3 # 9 : 27
t16 = t2 * t4 # 10 : 29
t1 = t10 * t1 # 11 : 31
t11 = t12 * t4 # 12 : 33
t8 = t1 * t3 # 13 : 39
t6 = t10 * t4 # 14 : 41
t3 = t1 * t4 # 15 : 45
t5 = t11 * t4 # 16 : 47
t15 = t3 * t0 # 17 : 51
t14 = t15 * t0 # 18 : 57
t7 = t5 * t4 # 19 : 61
t4 = t14 * t0 # 20 : 63
t0 = sqr(t14) # 21 : 114
t0 = sqr(t0) # 22 : 228
t0 = sqr(t0) # 23 : 456
t0 = sqr(t0) # 24 : 912
t0 = sqr(t0) # 25 : 1824
t0 = sqr(t0) # 26 : 3648
t0 = t0 * t7 # 27 : 3709
t0 = sqr(t0) # 28 : 7418
t0 = sqr(t0) # 29 : 14836
t0 = sqr(t0) # 30 : 29672
t0 = sqr(t0) # 31 : 59344
t0 = sqr(t0) # 32 : 118688
t0 = sqr(t0) # 33 : 237376
t0 = t0 * t3 # 34 : 237421
t0 = sqr(t0) # 35 : 474842
t0 = sqr(t0) # 36 : 949684
t0 = sqr(t0) # 37 : 1899368
t0 = sqr(t0) # 38 : 3798736
t0 = sqr(t0) # 39 : 7597472
t0 = sqr(t0) # 40 : 15194944
t0 = sqr(t0) # 41 : 30389888
t0 = t0 * t16 # 42 : 30389917
t0 = sqr(t0) # 43 : 60779834
t0 = sqr(t0) # 44 : 121559668
t0 = sqr(t0) # 45 : 243119336
t0 = sqr(t0) # 46 : 486238672
t0 = sqr(t0) # 47 : 972477344
t0 = sqr(t0) # 48 : 1944954688
t0 = t0 * t12 # 49 : 1944954707
t0 = sqr(t0) # 50 : 3889909414
t0 = sqr(t0) # 51 : 7779818828
t0 = sqr(t0) # 52 : 15559637656
t0 = sqr(t0) # 53 : 31119275312
t0 = sqr(t0) # 54 : 62238550624
t0 = sqr(t0) # 55 : 124477101248
t0 = sqr(t0) # 56 : 248954202496
t0 = sqr(t0) # 57 : 497908404992
t0 = t0 * t6 # 58 : 497908405033
t0 = sqr(t0) # 59 : 995816810066
t0 = sqr(t0) # 60 : 1991633620132
t0 = sqr(t0) # 61 : 3983267240264
t0 = sqr(t0) # 62 : 7966534480528
t0 = sqr(t0) # 63 : 15933068961056
t0 = sqr(t0) # 64 : 31866137922112
t0 = t0 * t8 # 65 : 31866137922151
t0 = sqr(t0) # 66 : 63732275844302
t0 = sqr(t0) # 67 : 127464551688604
t0 = sqr(t0) # 68 : 254929103377208
t0 = sqr(t0) # 69 : 509858206754416
t0 = sqr(t0) # 70 : 1019716413508832
t0 = sqr(t0) # 71 : 2039432827017664
t0 = sqr(t0) # 72 : 4078865654035328
t0 = t0 * t5 # 73 : 4078865654035375
t0 = sqr(t0) # 74 : 8157731308070750
t0 = sqr(t0) # 75 : 16315462616141500
t0 = sqr(t0) # 76 : 32630925232283000
t0 = sqr(t0) # 77 : 65261850464566000
t0 = sqr(t0) # 78 : 130523700929132000
t0 = t0 * t9 # 79 : 130523700929132021
t0 = sqr(t0) # 80 : 261047401858264042
t0 = sqr(t0) # 81 : 522094803716528084
t0 = sqr(t0) # 82 : 1044189607433056168
t0 = t0 * t13 # 83 : 1044189607433056169
t0 = sqr(t0) # 84 : 2088379214866112338
t0 = sqr(t0) # 85 : 4176758429732224676
t0 = sqr(t0) # 86 : 8353516859464449352
t0 = sqr(t0) # 87 : 16707033718928898704
t0 = sqr(t0) # 88 : 33414067437857797408
t0 = sqr(t0) # 89 : 66828134875715594816
t0 = sqr(t0) # 90 : 133656269751431189632
t0 = sqr(t0) # 91 : 267312539502862379264
t0 = sqr(t0) # 92 : 534625079005724758528
t0 = sqr(t0) # 93 : 1069250158011449517056
t0 = sqr(t0) # 94 : 2138500316022899034112
t0 = t0 * t15 # 95 : 2138500316022899034163
t0 = sqr(t0) # 96 : 4277000632045798068326
t0 = sqr(t0) # 97 : 8554001264091596136652
t0 = sqr(t0) # 98 : 17108002528183192273304
t0 = sqr(t0) # 99 : 34216005056366384546608
t0 = sqr(t0) # 100 : 68432010112732769093216
t0 = sqr(t0) # 101 : 136864020225465538186432
t0 = sqr(t0) # 102 : 273728040450931076372864
t0 = sqr(t0) # 103 : 547456080901862152745728
t0 = t0 * t14 # 104 : 547456080901862152745785
t0 = sqr(t0) # 105 : 1094912161803724305491570
t0 = sqr(t0) # 106 : 2189824323607448610983140
t0 = sqr(t0) # 107 : 4379648647214897221966280
t0 = sqr(t0) # 108 : 8759297294429794443932560
t0 = sqr(t0) # 109 : 17518594588859588887865120
t0 = t0 * t10 # 110 : 17518594588859588887865147
t0 = sqr(t0) # 111 : 35037189177719177775730294
t0 = sqr(t0) # 112 : 70074378355438355551460588
t0 = sqr(t0) # 113 : 140148756710876711102921176
t0 = sqr(t0) # 114 : 280297513421753422205842352
t0 = sqr(t0) # 115 : 560595026843506844411684704
t0 = sqr(t0) # 116 : 1121190053687013688823369408
t0 = sqr(t0) # 117 : 2242380107374027377646738816
t0 = sqr(t0) # 118 : 4484760214748054755293477632
t0 = t0 * t13 # 119 : 4484760214748054755293477633
t0 = sqr(t0) # 120 : 8969520429496109510586955266
t0 = sqr(t0) # 121 : 17939040858992219021173910532
t0 = sqr(t0) # 122 : 35878081717984438042347821064
t0 = sqr(t0) # 123 : 71756163435968876084695642128
t0 = sqr(t0) # 124 : 143512326871937752169391284256
t0 = sqr(t0) # 125 : 287024653743875504338782568512
t0 = sqr(t0) # 126 : 574049307487751008677565137024
t0 = sqr(t0) # 127 : 1148098614975502017355130274048
t0 = sqr(t0) # 128 : 2296197229951004034710260548096
t0 = sqr(t0) # 129 : 4592394459902008069420521096192
t0 = sqr(t0) # 130 : 9184788919804016138841042192384
t0 = sqr(t0) # 131 : 18369577839608032277682084384768
t0 = t0 * t12 # 132 : 18369577839608032277682084384787
t0 = sqr(t0) # 133 : 36739155679216064555364168769574
t0 = sqr(t0) # 134 : 73478311358432129110728337539148
t0 = sqr(t0) # 135 : 146956622716864258221456675078296
t0 = sqr(t0) # 136 : 293913245433728516442913350156592
t0 = sqr(t0) # 137 : 587826490867457032885826700313184
t0 = sqr(t0) # 138 : 1175652981734914065771653400626368
t0 = sqr(t0) # 139 : 2351305963469828131543306801252736
t0 = t0 * t11 # 140 : 2351305963469828131543306801252769
t0 = sqr(t0) # 141 : 4702611926939656263086613602505538
t0 = sqr(t0) # 142 : 9405223853879312526173227205011076
t0 = sqr(t0) # 143 : 18810447707758625052346454410022152
t0 = sqr(t0) # 144 : 37620895415517250104692908820044304
t0 = sqr(t0) # 145 : 75241790831034500209385817640088608
t0 = t0 * t10 # 146 : 75241790831034500209385817640088635
t0 = sqr(t0) # 147 : 150483581662069000418771635280177270
t0 = sqr(t0) # 148 : 300967163324138000837543270560354540
t0 = sqr(t0) # 149 : 601934326648276001675086541120709080
t0 = sqr(t0) # 150 : 1203868653296552003350173082241418160
t0 = sqr(t0) # 151 : 2407737306593104006700346164482836320
t0 = sqr(t0) # 152 : 4815474613186208013400692328965672640
t0 = sqr(t0) # 153 : 9630949226372416026801384657931345280
t0 = sqr(t0) # 154 : 19261898452744832053602769315862690560
t0 = sqr(t0) # 155 : 38523796905489664107205538631725381120
t0 = sqr(t0) # 156 : 77047593810979328214411077263450762240
t0 = sqr(t0) # 157 : 154095187621958656428822154526901524480
t0 = sqr(t0) # 158 : 308190375243917312857644309053803048960
t0 = sqr(t0) # 159 : 616380750487834625715288618107606097920
t0 = t0 * t9 # 160 : 616380750487834625715288618107606097941
t0 = sqr(t0) # 161 : 1232761500975669251430577236215212195882
t0 = sqr(t0) # 162 : 2465523001951338502861154472430424391764
t0 = sqr(t0) # 163 : 4931046003902677005722308944860848783528
t0 = sqr(t0) # 164 : 9862092007805354011444617889721697567056
t0 = sqr(t0) # 165 : 19724184015610708022889235779443395134112
t0 = sqr(t0) # 166 : 39448368031221416045778471558886790268224
t0 = sqr(t0) # 167 : 78896736062442832091556943117773580536448
t0 = t0 * t8 # 168 : 78896736062442832091556943117773580536487
t0 = sqr(t0) # 169 : 157793472124885664183113886235547161072974
t0 = sqr(t0) # 170 : 315586944249771328366227772471094322145948
t0 = sqr(t0) # 171 : 631173888499542656732455544942188644291896
t0 = sqr(t0) # 172 : 1262347776999085313464911089884377288583792
t0 = sqr(t0) # 173 : 2524695553998170626929822179768754577167584
t0 = sqr(t0) # 174 : 5049391107996341253859644359537509154335168
t0 = sqr(t0) # 175 : 10098782215992682507719288719075018308670336
t0 = t0 * t7 # 176 : 10098782215992682507719288719075018308670397
t0 = sqr(t0) # 177 : 20197564431985365015438577438150036617340794
t0 = sqr(t0) # 178 : 40395128863970730030877154876300073234681588
t0 = sqr(t0) # 179 : 80790257727941460061754309752600146469363176
t0 = sqr(t0) # 180 : 161580515455882920123508619505200292938726352
t0 = sqr(t0) # 181 : 323161030911765840247017239010400585877452704
t0 = sqr(t0) # 182 : 646322061823531680494034478020801171754905408
t0 = t0 * t6 # 183 : 646322061823531680494034478020801171754905449
t0 = sqr(t0) # 184 : 1292644123647063360988068956041602343509810898
t0 = sqr(t0) # 185 : 2585288247294126721976137912083204687019621796
t0 = sqr(t0) # 186 : 5170576494588253443952275824166409374039243592
t0 = sqr(t0) # 187 : 10341152989176506887904551648332818748078487184
t0 = sqr(t0) # 188 : 20682305978353013775809103296665637496156974368
t0 = sqr(t0) # 189 : 41364611956706027551618206593331274992313948736
t0 = sqr(t0) # 190 : 82729223913412055103236413186662549984627897472
t0 = sqr(t0) # 191 : 165458447826824110206472826373325099969255794944
t0 = sqr(t0) # 192 : 330916895653648220412945652746650199938511589888
t0 = sqr(t0) # 193 : 661833791307296440825891305493300399877023179776
t0 = sqr(t0) # 194 : 1323667582614592881651782610986600799754046359552
t0 = sqr(t0) # 195 : 2647335165229185763303565221973201599508092719104
t0 = sqr(t0) # 196 : 5294670330458371526607130443946403199016185438208
t0 = sqr(t0) # 197 : 10589340660916743053214260887892806398032370876416
t0 = t0 * t5 # 198 : 10589340660916743053214260887892806398032370876463
t0 = sqr(t0) # 199 : 21178681321833486106428521775785612796064741752926
t0 = sqr(t0) # 200 : 42357362643666972212857043551571225592129483505852
t0 = sqr(t0) # 201 : 84714725287333944425714087103142451184258967011704
t0 = sqr(t0) # 202 : 169429450574667888851428174206284902368517934023408
t0 = sqr(t0) # 203 : 338858901149335777702856348412569804737035868046816
t0 = sqr(t0) # 204 : 677717802298671555405712696825139609474071736093632
t0 = t0 * t4 # 205 : 677717802298671555405712696825139609474071736093695
t0 = sqr(t0) # 206 : 1355435604597343110811425393650279218948143472187390
t0 = sqr(t0) # 207 : 2710871209194686221622850787300558437896286944374780
t0 = sqr(t0) # 208 : 5421742418389372443245701574601116875792573888749560
t0 = sqr(t0) # 209 : 10843484836778744886491403149202233751585147777499120
t0 = sqr(t0) # 210 : 21686969673557489772982806298404467503170295554998240
t0 = t0 * t1 # 211 : 21686969673557489772982806298404467503170295554998271
t0 = sqr(t0) # 212 : 43373939347114979545965612596808935006340591109996542
t0 = sqr(t0) # 213 : 86747878694229959091931225193617870012681182219993084
t0 = sqr(t0) # 214 : 173495757388459918183862450387235740025362364439986168
t0 = sqr(t0) # 215 : 346991514776919836367724900774471480050724728879972336
t0 = sqr(t0) # 216 : 693983029553839672735449801548942960101449457759944672
t0 = sqr(t0) # 217 : 1387966059107679345470899603097885920202898915519889344
t0 = sqr(t0) # 218 : 2775932118215358690941799206195771840405797831039778688
t0 = sqr(t0) # 219 : 5551864236430717381883598412391543680811595662079557376
t0 = t0 * t3 # 220 : 5551864236430717381883598412391543680811595662079557421
t0 = sqr(t0) # 221 : 11103728472861434763767196824783087361623191324159114842
t0 = sqr(t0) # 222 : 22207456945722869527534393649566174723246382648318229684
t0 = sqr(t0) # 223 : 44414913891445739055068787299132349446492765296636459368
t0 = sqr(t0) # 224 : 88829827782891478110137574598264698892985530593272918736
t0 = t0 * t2 # 225 : 88829827782891478110137574598264698892985530593272918751
t0 = sqr(t0) # 226 : 177659655565782956220275149196529397785971061186545837502
t0 = sqr(t0) # 227 : 355319311131565912440550298393058795571942122373091675004
t0 = sqr(t0) # 228 : 710638622263131824881100596786117591143884244746183350008
t0 = sqr(t0) # 229 : 1421277244526263649762201193572235182287768489492366700016
t0 = sqr(t0) # 230 : 2842554489052527299524402387144470364575536978984733400032
t0 = t0 * t1 # 231 : 2842554489052527299524402387144470364575536978984733400063
t0 = sqr(t0) # 232 : 5685108978105054599048804774288940729151073957969466800126
t0 = sqr(t0) # 233 : 11370217956210109198097609548577881458302147915938933600252
t0 = sqr(t0) # 234 : 22740435912420218396195219097155762916604295831877867200504
t0 = sqr(t0) # 235 : 45480871824840436792390438194311525833208591663755734401008
t0 = sqr(t0) # 236 : 90961743649680873584780876388623051666417183327511468802016
t0 = sqr(t0) # 237 : 181923487299361747169561752777246103332834366655022937604032
t0 = sqr(t0) # 238 : 363846974598723494339123505554492206665668733310045875208064
t0 = sqr(t0) # 239 : 727693949197446988678247011108984413331337466620091750416128
t0 = sqr(t0) # 240 : 1455387898394893977356494022217968826662674933240183500832256
t0 = sqr(t0) # 241 : 2910775796789787954712988044435937653325349866480367001664512
t0 = sqr(t0) # 242 : 5821551593579575909425976088871875306650699732960734003329024
t0 = sqr(t0) # 243 : 11643103187159151818851952177743750613301399465921468006658048
t0 = sqr(t0) # 244 : 23286206374318303637703904355487501226602798931842936013316096
t0 = sqr(t0) # 245 : 46572412748636607275407808710975002453205597863685872026632192
t0 = sqr(t0) # 246 : 93144825497273214550815617421950004906411195727371744053264384
t0 = sqr(t0) # 247 : 186289650994546429101631234843900009812822391454743488106528768
t0 = sqr(t0) # 248 : 372579301989092858203262469687800019625644782909486976213057536
t0 = sqr(t0) # 249 : 745158603978185716406524939375600039251289565818973952426115072
t0 = sqr(t0) # 250 : 1490317207956371432813049878751200078502579131637947904852230144
t0 = sqr(t0) # 251 : 2980634415912742865626099757502400157005158263275895809704460288
t0 = sqr(t0) # 252 : 5961268831825485731252199515004800314010316526551791619408920576
t0 = sqr(t0) # 253 : 11922537663650971462504399030009600628020633053103583238817841152
t0 = sqr(t0) # 254 : 23845075327301942925008798060019201256041266106207166477635682304
t0 = sqr(t0) # 255 : 47690150654603885850017596120038402512082532212414332955271364608
t0 = sqr(t0) # 256 : 95380301309207771700035192240076805024165064424828665910542729216
t0 = sqr(t0) # 257 : 190760602618415543400070384480153610048330128849657331821085458432
t0 = sqr(t0) # 258 : 381521205236831086800140768960307220096660257699314663642170916864
t0 = sqr(t0) # 259 : 763042410473662173600281537920614440193320515398629327284341833728
t0 = sqr(t0) # 260 : 1526084820947324347200563075841228880386641030797258654568683667456
t0 = sqr(t0) # 261 : 3052169641894648694401126151682457760773282061594517309137367334912
t0 = sqr(t0) # 262 : 6104339283789297388802252303364915521546564123189034618274734669824
# Bos-Coster (win=5) : 263 (17)
t
:
let t13 = input;
let t1 = t13.square();
let mut t3 = t1.square();
let t2 = t3 * &t1;
let t4 = t2.square();
let t0 = t4 * &t2;
let t12 = t0 * &t13;
let t9 = t12 * &t1;
let t10 = t9 * &t2;
let t16 = t10 * &t1;
let t1 = t12 * &t4;
let t11 = t9 * &t4;
let t8 = t9 * &t0;
let t6 = t16 * &t4;
let t4 = t10 * &t0;
let t5 = t16 * &t0;
let t15 = t11 * &t0;
t3.mul_assign(&t15);
let t14 = t8 * &t0;
let t7 = t3 * &t2;
let t2 = t4 * &t0;
let mut t0 = t14.square();
square_assign_multi(&mut t0, 5);
t0.mul_assign(&t7);
square_assign_multi(&mut t0, 6);
t0.mul_assign(&t4);
square_assign_multi(&mut t0, 7);
t0.mul_assign(&t16);
square_assign_multi(&mut t0, 6);
t0.mul_assign(&t12);
square_assign_multi(&mut t0, 8);
t0.mul_assign(&t6);
square_assign_multi(&mut t0, 6);
t0.mul_assign(&t8);
square_assign_multi(&mut t0, 7);
t0.mul_assign(&t5);
square_assign_multi(&mut t0, 5);
t0.mul_assign(&t9);
square_assign_multi(&mut t0, 3);
t0.mul_assign(&t13);
square_assign_multi(&mut t0, 11);
t0.mul_assign(&t15);
square_assign_multi(&mut t0, 8);
t0.mul_assign(&t14);
square_assign_multi(&mut t0, 5);
t0.mul_assign(&t10);
square_assign_multi(&mut t0, 8);
t0.mul_assign(&t13);
square_assign_multi(&mut t0, 12);
t0.mul_assign(&t12);
square_assign_multi(&mut t0, 7);
t0.mul_assign(&t11);
square_assign_multi(&mut t0, 5);
t0.mul_assign(&t10);
square_assign_multi(&mut t0, 13);
t0.mul_assign(&t9);
square_assign_multi(&mut t0, 7);
t0.mul_assign(&t8);
square_assign_multi(&mut t0, 7);
t0.mul_assign(&t7);
square_assign_multi(&mut t0, 6);
t0.mul_assign(&t6);
square_assign_multi(&mut t0, 14);
t0.mul_assign(&t5);
square_assign_multi(&mut t0, 6);
t0.mul_assign(&t2);
square_assign_multi(&mut t0, 5);
t0.mul_assign(&t1);
square_assign_multi(&mut t0, 8);
t0.mul_assign(&t4);
square_assign_multi(&mut t0, 6);
t0.mul_assign(&t2);
square_assign_multi(&mut t0, 6);
t0.mul_assign(&t3);
square_assign_multi(&mut t0, 6);
t0.mul_assign(&t2);
square_assign_multi(&mut t0, 6);
t0.mul_assign(&t2);
square_assign_multi(&mut t0, 6);
t0.mul_assign(&t2);
square_assign_multi(&mut t0, 6);
t0.mul_assign(&t2);
square_assign_multi(&mut t0, 5);
t0.mul_assign(&t1);
(t-1)/2
:
let t13 = input;
let mut t0 = t13.square();
let mut t1 = t0.square();
t0.mul_assign(&t1);
let t3 = t1.square();
let t4 = t3 * &t0;
let t2 = t4 * &t13;
let t12 = t2 * &t1;
let t9 = t2 * &t0;
let t10 = t12 * &t3;
let t16 = t2 * &t4;
t1.mul_assign(&t10);
let t11 = t12 * &t4;
let t8 = t1 * &t3;
let t6 = t10 * &t4;
let t3 = t1 * &t4;
let t5 = t11 * &t4;
let t15 = t3 * &t0;
let t14 = t15 * &t0;
let t7 = t5 * &t4;
let t4 = t14 * &t0;
let mut t0 = t14.square();
square_assign_multi(&mut t0, 5);
t0.mul_assign(&t7);
square_assign_multi(&mut t0, 6);
t0.mul_assign(&t3);
square_assign_multi(&mut t0, 7);
t0.mul_assign(&t16);
square_assign_multi(&mut t0, 6);
t0.mul_assign(&t12);
square_assign_multi(&mut t0, 8);
t0.mul_assign(&t6);
square_assign_multi(&mut t0, 6);
t0.mul_assign(&t8);
square_assign_multi(&mut t0, 7);
t0.mul_assign(&t5);
square_assign_multi(&mut t0, 5);
t0.mul_assign(&t9);
square_assign_multi(&mut t0, 3);
t0.mul_assign(&t13);
square_assign_multi(&mut t0, 11);
t0.mul_assign(&t15);
square_assign_multi(&mut t0, 8);
t0.mul_assign(&t14);
square_assign_multi(&mut t0, 5);
t0.mul_assign(&t10);
square_assign_multi(&mut t0, 8);
t0.mul_assign(&t13);
square_assign_multi(&mut t0, 12);
t0.mul_assign(&t12);
square_assign_multi(&mut t0, 7);
t0.mul_assign(&t11);
square_assign_multi(&mut t0, 5);
t0.mul_assign(&t10);
square_assign_multi(&mut t0, 13);
t0.mul_assign(&t9);
square_assign_multi(&mut t0, 7);
t0.mul_assign(&t8);
square_assign_multi(&mut t0, 7);
t0.mul_assign(&t7);
square_assign_multi(&mut t0, 6);
t0.mul_assign(&t6);
square_assign_multi(&mut t0, 14);
t0.mul_assign(&t5);
square_assign_multi(&mut t0, 6);
t0.mul_assign(&t4);
square_assign_multi(&mut t0, 5);
t0.mul_assign(&t1);
square_assign_multi(&mut t0, 8);
t0.mul_assign(&t3);
square_assign_multi(&mut t0, 4);
t0.mul_assign(&t2);
square_assign_multi(&mut t0, 5);
t0.mul_assign(&t1);
square_assign_multi(&mut t0, 31);
Jubjub needs you!
... to make efficient addition chains.
0x73eda753299d7d483339d80809a1d80553bda402fffe5bfefffffffeffffffff
(for inversion in Fq)0x39f6d3a994cebea4199cec0404d0ec02a9ded2017fff2dff7fffffff80000000
(for Legendre symbol in Fq)0x39f6d3a994cebea4199cec0404d0ec02a9ded2017fff2dff80000000
(for sqrt in Fq)0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff
(also for sqrt in Fq)0x0e7db4ea6533afa906673b0101343b00a6682093ccc81082d0970e5ed6f72cb5
(for inversion in Fr)