compute-awc-swb-period-length.py 3.59 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101
#!/bin/bash

# Copyright 2019 Christoph Conrads
#
# This Source Code Form is subject to the terms of the Mozilla Public
# License, v. 2.0. If a copy of the MPL was not distributed with this
# file, You can obtain one at http://mozilla.org/MPL/2.0/.

import collections
import operator
import math



def main():
    factors_32_17_3 = [3, 5, 17, 29, 43, 113, 127, 257, 449, 641, 5153, 2689,
            65537, 6700417, 15790321, 54410972897, 183076097,
            167773885276849215533569, 358429848460993,
            37414057161322375957408148834323969]
    ps_32_17_3 = collections.Counter(factors_32_17_3)
    ps_32_17_3[2] = 32*3

    factors_32_26_14 = [3, 3, 5, 7, 13, 17, 97, 193, 241, 257, 641, 673, 769,
            65537, 274177, 6700417, 22253377, 18446744069414584321,
            67280421310721, 442499826945303593556473164314770689]
    ps_32_26_14 = collections.Counter(factors_32_26_14)
    ps_32_26_14[2] = 32*14

    factors_32_37_24 = [3, 5, 17, 53, 157, 257, 1613, 2731, 8191, 928513,
            858001, 65537, 308761441, 18558466369, 23877647873, 21316654212673,
            715668470267111297, 78919881726271091143763623681]
    ps_32_37_24 = collections.Counter(factors_32_37_24)
    ps_32_37_24[2] = 32*24

    factors_64_26_4 = [3, 5, 17, 23, 89, 257, 353, 397, 641, 683, 1409, 2113,
            65537, 229153, 5304641, 274177, 119782433, 43872038849, 1258753,
            6700417, 2931542417, 67280421310721, 441995541378330835457,
            60299259845689822028046342401,
            275509565477848842604777623828011666349761,
            3210843755324367119258027752661239735297]
    ps_64_26_4 = collections.Counter(factors_64_26_4)
    ps_64_26_4[2] = 64*4

    factors_awc_32_8_3 = [2, 87956635234305, 37217928793913440210506431,
            17685937523735152413434380411781231297]
    ps_awc_32_8_3 = collections.Counter(factors_awc_32_8_3)

    factors_awc_32_8_3 = [2, 87956635234305, 37217928793913440210506431,
            17685937523735152413434380411781231297]
    ps_awc_32_8_3 = collections.Counter(factors_awc_32_8_3)

    factors_awc_32_16_3 = [2, 3, 5, 11, 17, 29, 257, 82387, 65537,
            156687811973560733, 2696785382316285340445273,
            140551974055502473133117533007407559678958241229948687231152346988198330311395265590556890646801]
    ps_awc_32_16_3 = collections.Counter(factors_awc_32_16_3)

    factors_awc_32_29_17 = [2, 3, 5, 17, 23, 257, 65537, 7165729, 16261579,
            296174737, 9286471429,
            35834095934305889246278160558607808213536611909101400963631213603354576647919834164787160509080753251812869864745539853004298715922465713710357103697213980386700856246837790064184164935087482021935440410696100869139134472551164881019937]
    ps_awc_32_29_17 = collections.Counter(factors_awc_32_29_17)

    e = 64
    r = 26
    s = 4
    b = 2**e

    m = b**r - b**s + 1

    print('b=2^{:d} r={:d} s={:d}'.format(e, r, s))

    d = m-1

    ps = ps_64_26_4
    q = reduce(operator.mul, factors_64_26_4, 1)

    print(((m-1) / b**s) % q)
    print(((m-1) / b**s) // q)

    print('Found {:d} prime factors'.format(len(ps)))

    #assert reduce(operator.mul, ps, 1) == m-1
    print((m-1) % (q * b**s))
    print((m-1) // (q * b**s))


    # https://math.stackexchange.com/questions/1025578/is-there-a-better-way-of-finding-the-order-of-a-number-modulo-n
    for p in sorted(ps.keys()):
        for n in xrange(ps[p]):
            r = pow(b, d/p, m)

            if r == 1:
                d = d // p

    period10 = math.log10(d)
    period2 = math.log(d) / math.log(2)

    print('Period length  2^{:.2f}  10^{:.2f}'.format(period2, period10))


if __name__ == '__main__':
    main()