Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Request for Addition Chains #1

Open
ebfull opened this issue Sep 1, 2018 · 6 comments
Open

Request for Addition Chains #1

ebfull opened this issue Sep 1, 2018 · 6 comments

Comments

@ebfull
Copy link
Contributor

ebfull commented Sep 1, 2018 •
edited

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
Copy link

ValarDragon commented Sep 1, 2018 •
edited

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
Copy link
Contributor Author

ebfull commented Sep 1, 2018

Thanks @ValarDragon!

@Eirik0 Eirik0 mentioned this issue Sep 19, 2018
Merged
@Eirik0
Copy link
Contributor

Eirik0 commented Sep 26, 2018

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

@Eirik0
Copy link
Contributor

Eirik0 commented Feb 11, 2019

#12 implemented the addition chain referenced above for Fr.

@str4d
Copy link
Member

str4d commented Feb 27, 2019

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
Copy link
Contributor

Eirik0 commented Feb 27, 2019 •
edited

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

@mmcloughlin mmcloughlin mentioned this issue Apr 28, 2021
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
4 participants
@ebfull @str4d @Eirik0 @ValarDragon