Request for Addition Chains

[ebfull]

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)

[ValarDragon]

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

[ebfull]

Thanks @ValarDragon!

[Eirik0]

For reference:
https://github.com/Eirik0/add-chain-converter

[Eirik0]

#12 implemented the addition chain referenced above for Fr.

[str4d]

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)

[Eirik0]

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);