rare-dev - Re: [rare-dev] polka is approaching rare... was: Re: custom crc32 library in freerouter

Subject: Rare project developers

List archive

Re: [rare-dev] polka is approaching rare... was: Re: custom crc32 library in freerouter

From: mc36 <>
To: Cristina Klippel Dominicini <>
Cc: Rafael Silva Guimarães <>, "" <>, "Moises R. N. Ribeiro" <>, Magnos Martinello <>
Subject: Re: [rare-dev] polka is approaching rare... was: Re: custom crc32 library in freerouter
Date: Wed, 27 Oct 2021 14:28:02 +0200

hi,
as said before, i came up with my own poly.java which is specific to gf(2),
had add,sub,mul,div and modinv...
at the moment it have an S generator and a checker... below is a test run,
first some basic poly math, then
your paper's calculation, which is fine, then a randomly generated S and O,
encoding of R and verification of it...
everything seems fine at least as i see, but i have issues with your
polka.patch... there, you propose the numbers
0x2b,0x2d,0x39,0x3f,0x47,0x53,0x8d,0xbd,0xd7,0xf5, i checked some and it
seems to me that these are not irreducible...
for an example, i picked up randomly 0x3f and 0x53 and according to my poly
lib, it have a gcm of 1001... you can verify it at
http://www.ee.unb.ca/cgi-bin/tervo/calc.pl?num=111111&den=1001&f=d and
http://www.ee.unb.ca/cgi-bin/tervo/calc.pl?num=1010011&den=1001&f=d
both of them give back 000 as remainder...
as for now, i have everything, i'll slowly integrate it to freerouter to see
how it fits... :)
seeking for your comments,
regards,
cs

100 = 100
11011 = 11011
1001001000 = 1001001000
1001001001001001 = 1001001001001001
1110111 = 1110111
111110111110000000000 = 111110111110000000000
a=111011 n=1111111111110000000 inv=110001111001100111 gcd=1
verify=1
a=111111 n=1010011 inv=null gcd=1001
a=1010011 n=111111 inv=null gcd=1001
****************************************************
M=1010011
i=0 Si=11 Mi=110001 Ni=1 verify=1
i=1 Si=111 Mi=11101 Ni=1 verify=1
i=2 Si=1011 Mi=1001 Ni=101 verify=1
r~=11100101 r=10000
i=0 Oi=1 O~i=1 cmp=0
i=1 Oi=10 O~i=10 cmp=0
i=2 Oi=110 O~i=110 cmp=0
****************************************************
M=1000100101010111000000111101111001010011000011001110110010110011001000001001000101010011001101001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000100101010111000000111101111001010011000011001110110010110011001000001001000101010011001101001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100010010101011100000011110111100101001100001100111011001011001100100000100100010101001100110100100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100010010101011100000011110111100101001100001100111011001011001100100000100100010101001100110100100000000
i=0 Si=100000000 Mi=10001001010101110000001111011110010100110000110011101100101100110010000010010001010100110011010010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010001001010101110000001111011110010100110000110011101100101100110010000010010001010100110011010010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000100101010111000000111101111001010011000011001110110010110011001000001001000101010011001101001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000100101010111000000111101111001010011000011001110110010110011001000001001000101010011001101001 Ni=101001 verify=1
i=1 Si=100000001 Mi=10001001110111101101110100000011010100000101110010110000000000110010001110110010111000011101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101000100011011101000111011110101001111110101111011000011010101010011000100100011000010010110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111011000100001001000101111110010101111101000110100111111111100110111000100110100011110001010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101011101110010001011100010000101011000000101000010011110010101010110011101101110011110110100100000000 Ni=10111001 verify=1
i=2 Si=100000011 Mi=10001000110011100101000100101101001001000110000001001100011001111000100000001001010010001110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110100111110000101010011110010011011111111110000110111111010101111001110010110111111100100111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000100011001110010100010010110100100100011000000100110001100111100010000000100101001000111011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011010011111000010101001111001001101111111111000011011111101010111100111001011011111110010011100000000 Ni=1010000 verify=1
i=3 Si=100000101 Mi=10001011111100110011110000010010000010010010000101001000110110001001101001100010101110110110001001101011110001001101011110001001101011110001001101011110001001101011110001001101011110001001101011110001001101011110001001101011110001001101011110001001101011100000010010111000010111101001100001011111001110100000101101000000000000010010011100011101000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000101111110011001111000001001000001001001000010100100011011000100110100110001010111011011000100110101111000100110101111000100110101111000100110101111000100110101111000100110101111000100110101111000100110101111000100110101111000100110101111000100110101110000001001011100001011110100110000101111100111010000010110100000000000001001001110001110100000000 Ni=10010100 verify=1
i=4 Si=100001001 Mi=10001101101101110000110010110111010111101010011101110000010000010110101010101110100010011111001011100101110010111001011100101110010111001011100101110010111001011100101110010111001011100101110010111001011100101110010111001011100101110010111001011100101110000110100110001011110100101111100110010011000100100101100111110000001100001001011010000100110010111001011100101110010111001011100101110010111001011100101110010111001011100101110010111001011100101110010111001011100101110010111001011100101110010111001011100100110100001111100100110111001100100000010000111100000001010100100101000010011100110100111101011100101110010111001011100101110010111001011100101110010111001011100101110010111001011100101110010111001011100101110010111001011100101110010111001011100101110010110001101010011001010100000000111000101100010000101011101111010110010001001111001000110000100000000 Ni=110011 verify=1
i=5 Si=100001111 Mi=10001110100010101110000001111100110000110101111010000001001111010111100100110111011011000101001110100111010011101001110100111010011101001110100111010011101001110100111010011101001110100111010011101001110100111010011101001110100111010011101001110100111010001100111010110010100011100110010010111100110010011110101110101001010101010010000001000101100111010011101001110100111010011101001110100111010011101001110100111010011101001110100111010011101001110100111010011101001110100111010011101001110100111010011101001111100000000010111110110100000100000101010100011010010011001110011111001000000110100011000101110100111010011101001110100111010011101001110100111010011101001110100111010011101001110100111010011101001110100111010011101001110100111010011101001110100111010011100001001110110000100101001001010100010000111110011100111110100000010000110100001110000101100000000 Ni=1100000 verify=1
i=6 Si=100010111 Mi=10000010111101001000010000000010011110111101001011111111101101100100011100110111101011111000001000101100000001000101100000001000101100000001000101100000001000101100000001000101100000001000101100000001000101100000001000101100000001000101100000001000101100010001010010001001001010101100010010110010001001010111010001101101100110000110110101110011000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000001011110100100001000000001001111011110100101111111110110110010001110011011110101111100000100010110000000100010110000000100010110000000100010110000000100010110000000100010110000000100010110000000100010110000000100010110000000100010110000000100010110001000101001000100100101010110001001011001000100101011101000110110110011000011011010111001100000000 Ni=11001101 verify=1
i=7 Si=100011011 Mi=10000100101101000011110110101111001010011010000100010110010111101101100010110110010111101100110101101010010010000001100101110111010101100010100110101101010010010000001100101110111010101100010100110101101010010010000001100101110111010101100010100110101101000010110101100100110000001111010101000111100101001000100000111100001001100001100111011111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000010010110100001111011010111100101001101000010001011001011110110110001011011001011110110011010110101001001000000110010111011101010110001010011010110101001001000000110010111011101010110001010011010110101001001000000110010111011101010110001010011010110100001011010110010011000000111101010100011110010100100010000011110000100110000110011101111100000000 Ni=1001101 verify=1
i=8 Si=100011101 Mi=10000111100010100101011100011100000111100111111101100011011100010000110100010001100100010111110000101111000110100000001000111000100101110000001100100100110111001000001010110110101100101100001111101101111010111010001000011011000111100111001100010110100100000100010110001001011101111101011111101111110010111101111011011000101101011011011100000101000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000011110001010010101110001110000011110011111110110001101110001000011010001000110010001011111000010111100011010000000100011100010010111000000110010010011011100100000101011011010110010110000111110110111101011101000100001101100011110011100110001011010010000010001011000100101110111110101111110111111001011110111101101100010110101101101110000010100000000 Ni=10000011 verify=1
i=9 Si=100101011 Mi=10011111111101100110011010010011000111010110110110000110110101000111000110111001011111001100111001101100010111011011110010110110101110010010011010001110001001111010000111010110000010110010000001101110000000100101111111100011010101011110110011001010010001010101110000101110110110010011100100000101100010100101111010100100000011001100100010101111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001001111111110110011001101001001100011101011011011000011011010100011100011011100101111100110011100110110001011101101111001011011010111001001001101000111000100111101000011101011000001011001000000110111000000010010111111110001101010101111011001100101001000101010111000010111011011001001110010000010110001010010111101010010000001100110010001010111100000000 Ni=11011001 verify=1
i=10 Si=100101101 Mi=10011100110001100010100100111101110011100100000110010101011101101110011000011100010101100100000111110111011111101010010110101011001110010011001000101110001000111100101111000010100011010111110011110110010101110101101110011010011011010001001110110110000111000001110110011010011010100110000001001100100100011011010100001110110110010111101010110101000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001001110011000110001010010011110111001110010000011001010101110110111001100001110001010110010000011111011101111110101001011010101100111001001100100010111000100011110010111100001010001101011111001111011001010111010110111001101001101101000100111011011000011100000111011001101001101010011000000100110010010001101101010000111011011001011110101011010100000000 Ni=10110101 verify=1
i=11 Si=100111001 Mi=10010110110000111001011101101001110100110001010010000100110001010011100011111110011101110110001010001111111100010100011111111000101000111111110001010001111111100010100011111111000101000111111110001010001111111100010100011111111000101000111111110001010001101101010100100100110100101000001001011000000000011111011010011110000011100111011011010001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001001011011000011100101110110100111010011000101001000010011000101001110001111111001110111011000101000111111110001010001111111100010100011111111000101000111111110001010001111111100010100011111111000101000111111110001010001111111100010100011111111000101000110110101010010010011010010100000100101100000000001111101101001111000001110011101101101000100000000 Ni=1111001 verify=1
i=12 Si=100111111 Mi=10010101111100000101111010001010010110001101011111110101001001110111011011010000111101111100100000111101001011011100101011010101011110010001010000001101001111100110001001010010010000011110100101101110010101101010101111001000101000000110100111110011000100111011100111101111111101100110011000000100111100011010111101001101101000100011100101111011000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001001010111110000010111101000101001011000110101111111010100100111011101101101000011110111110010000011110100101101110010101101010101111001000101000000110100111110011000100101001001000001111010010110111001010110101010111100100010100000011010011111001100010011101110011110111111110110011001100000010011110001101011110100110110100010001110010111101100000000 Ni=11101 verify=1
i=13 Si=101001101 Mi=10100111101111001000101111010000010101011101010110101000110011011100010100100001100111111101110110101101001111111100110111101110100000001010110001100111000000111110100101010010000010000111011111101100001100010011000001101000101001101010000101110011110101101000100001010001111001110011001001011001100010000011111110110111010000010010011111010101000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001010011110111100100010111101000001010101110101011010100011001101110001010010000110011111110111011010110100111111110011011110111010000000101011000110011100000011111010010101001000001000011101111110110000110001001100000110100010100110101000010111001111010110100010000101000111100111001100100101100110001000001111111011011101000001001001111101010100000000 Ni=10101001 verify=1
i=14 Si=101011111 Mi=10101110000011100011011000001111001110100100111000010011100011101011100110001011111111110000000111101111111100111001100111100101101001101000111010010000011011110101011011001000100100101111101000010011000101011110000010001100000001010010101010001011101110111011100011110000010000000110000010100010111100011110010010010000001111001001111110011011000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001010111000001110001101100000111100111010010011100001001110001110101110011000101111111111000000011110111111110011100110011110010110100110100011101001000001101111010101101100100010010010111110100001001100010101111000001000110000000101001010101000101110111011101110001111000001000000011000001010001011110001111001001001000000111100100111111001101100000000 Ni=1010000 verify=1
i=15 Si=101100011 Mi=10110010010111010000010100111000000111110000111111111100001111110101110110101000100111101111010000011001010101000110101100011000001001011011010100110100111111011100110011110110010000100000011100100100110001001110101011010001000101001000111110000000101110011000101110101100011001100100110011011111010000000001110110010111111110000010011111000111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001011001001011101000001010011100000011111000011111111110000111111010111011010100010011110111101000001100101010100011010110001100000100101101101010011010011111101110011001111011001000010000001110010010011000100111010101101000100010100100011111000000010111001100010111010110001100110010011001101111101000000000111011001011111111000001001111100011100000000 Ni=10010010 verify=1
i=16 Si=101100101 Mi=10110001010111110000000011111101100010110000100011100011011010100010110010110100100001000010111001001101101001100110100011101101100010001001111010010010000111100010100111000111110101111001110100001010110010100010110000011001000110000110111111011100001000011111011110010001100000000011011101111100000100110010100110110011101000000000001001111101000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001011000101011111000000001111110110001011000010001110001101101010001011001011010010000100001011100100110110100110011010001110110110001000100111101001001000011110001010011100011111010111100111010000101011001010001011000001100100011000011011111101110000100001111101111001000110000000001101110111110000010011001010011011001110100000000000100111110100000000 Ni=1000010 verify=1
i=17 Si=101101001 Mi=10110111011011011100101111000011001001001011011010011011010010010101111100010000111000001111000110100000100100101110000110110111001000101101100101100111011010111010100110111100111110101100010100001111010011110001000111010001001100100111001101010110100101001001010101100101100110110100010001011100001010110000100101011000111111100111111100000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001011011101101101110010111100001100100100101101101001101101001001010111110001000011100000111100011010000010010010111000011011011100100010110110010110011101101011101010011011110011111010110001010000111101001111000100011101000100110010011100110101011010010100100101010110010110011011010001000101110000101011000010010101100011111110011111110000000100000000 Ni=11000111 verify=1
i=18 Si=101110001 Mi=10111011110111011100100111000011000000000000111001011010101110111011100111110100011100101001101001101011011010100000100111011001001001100000011101001000111000100000001011000111101000011111111001000010100111110101010111000001100010101100110010111111011110001100110000101110101110110001000010001100111110110011100011110011001011101001001110011001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001011101111011101110010011100001100000000000011100101101010111011101110011111010001110010100110100110101101101010000010011101100100100110000001110100100011100010000000101100011110100001111111100100001010011111010101011100000110001010110011001011111101111000110011000010111010111011000100001000110011111011001110001111001100101110100100111001100100000000 Ni=11001101 verify=1
i=19 Si=101110111 Mi=10111000110111000100100111111100110000010011001010100110110001100100110101011011111010010100011100000100111100110101001100100110111111110010001101101001110010100001000100000110001110000010011110011010100110010011011111111001000110110100111001010000100010010100000001111001101011110010110101001011110110101000010101010110111010000011001110010011000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001011100011011100010010011111110011000001001100101010011011000110010011010101101111101001010001110000010011110011010100110010011011111111001000110110100111001010000100010000011000111000001001111001101010011001001101111111100100011011010011100101000010001001010000000111100110101111001011010100101111011010100001010101011011101000001100111001001100000000 Ni=11 verify=1
i=20 Si=101111011 Mi=10111110111010100000111101110001001100001111011001110000100110100011011100101101011011110010001000010001111001100011001000101010010101100111111011111010100000110000111110000101000100001000111100110001100100010101001010110011111101111101010000011000011111010101010101010000011001110110111011101011011110010111111010001010110011101001100100111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001011111011101010000011110111000100110000111101100111000010011010001101110010110101101111001000100001000111100110001100100010101001010110011111101111101010000011000011111000010100010000100011110011000110010001010100101011001111110111110101000001100001111101010101010101000001100111011011101110101101111001011111101000101011001110100110010011111100000000 Ni=11100100 verify=1
i=21 Si=110000111 Mi=11110010111100101001010000100011001011001000110110001000000011011111111001001100110110011101000100100101010100110010111010001110110011111011010000001000001011110111011110000100111010110001111001101101111111101010111001110010011010100001101110000011000011111101011011110100100011111110001000001111110110110110111001001001001010110101110000100011000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111001011110010100101000010001100101100100011011000100000001101111111100100110011011001110100010010010101010011001011101000111011001111101101000000100000101111011101111000010011101011000111100110110111111110101011100111001001101010000110111000001100001111110101101111010010001111111000100000111111011011011011100100100100101011010111000010001100000000 Ni=1000 verify=1
i=22 Si=110001011 Mi=11110101010000110110100111001100010001101010001111100101001001100101000010111001100110011001110010000001000011011010110100010101000110101010110011100011110100110100101011110000111001000000100001101101011010001010100011010101011001110001111010011010010101100110110110100110100100001111001111001000000000010110000101110100010101011010000110001111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111010101000011011010011100110001000110101000111110010100100110010100001011100110011001100111001000000100001101101011010001010100011010101011001110001111010011010010101111000011100100000010000110110101101000101010001101010101100111000111101001101001010110011011011010011010010000111100111100100000000001011000010111010001010101101000011000111100000000 Ni=1010101 verify=1
i=23 Si=110001101 Mi=11110110100010101010010010001000110101000011000100011110001110000010111001011000110010110000110101100010101010011000001011101011111011011101100001010010111101001111111101010000111001111000011011001101000111101110001110100000001111100010010100010001011010110000100101110001110101010001100111100101100001000100101110010101110010010000010100010101000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111011010001010101001001000100011010100001100010001111000111000001011100101100011001011000011010110001010101001100000101110101111101101110110000101001011110100111111110101000011100111100001101100110100011110111000111010000000111110001001010001000101101011000010010111000111010101000110011110010110000100010010111001010111001001000001010001010100000000 Ni=11011101 verify=1
i=24 Si=110011111 Mi=11111101000101101101000001001110001100100011111110011010000001100100011000011100001110010111101100001110110111011100001001010000001000101001111101100001110110111011100001001010000001000101001111101100001110110111011100001001010000001000101001111101100001101001010011001100100010001000110100101011110011111101100111010000101010010011101001011011000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111110100010110110100000100111000110010001111111001101000000110010001100001110000111001011110110000111011011101110000100101000000100010100111110110000111011011101110000100101000000100010100111110110000111011011101110000100101000000100010100111110110000110100101001100110010001000100011010010101111001111110110011101000010101001001110100101101100000000 Ni=100001 verify=1
i=25 Si=110100011 Mi=11100111000101110110010010111000111110011101011110111101011011100110101001000101110001101100010110101101100001000000100111000011110101001011001011110001110011010101011000101010001011010110110000100000010011100001111010100101100101111000111001101010101100001001111101000101101010000111001110000011010110100101011001100000101001111101111000000111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001110011100010111011001001011100011111001110101111011110101101110011010100100010111000110110001011010110110000100000010011100001111010100101100101111000111001101010101100010101000101101011011000010000001001110000111101010010110010111100011100110101010110000100111110100010110101000011100111000001101011010010101100110000010100111110111100000011100000000 Ni=10000 verify=1
i=26 Si=110101001 Mi=11100011011111111010011011100010101000001101111000000011011110001111111110111000001101111000101111001000111000101100100100111010110110100111101101110100011011001110010110101001011101111101110011000011001010100010101111110011111000001010000100001111000110010100111110110011100100110110111001011110010101010000011100101001111011000011000111000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001110001101111111101001101110001010100000110111100000001101111000111111111011100000110111100010111100100011100010110010010011101011011010011110110111010001101100111001011010100101110111110111001100001100101010001010111111001111100000101000010000111100011001010011111011001110010011011011100101111001010101000001110010100111101100001100011100000100000000 Ni=11110000 verify=1
i=27 Si=110110001 Mi=11101100101110100110001010000111100101011010010100101011100111001011111111001101010000111101111001011111100110011101010000011011011111011110101111001011111100110011101010000011011011111011110101111001011111100110011101010000011011011111011110101111001011100001010110011110110010001011000111011110101011111010111010100100001111100010110101011001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001110110010111010011000101000011110010101101001010010101110011100101111111100110101000011110111100101111110011001110101000001101101111101111010111100101111110011001110101000001101101111101111010111100101111110011001110101000001101101111101111010111100101110000101011001111011001000101100011101111010101111101011101010010000111110001011010101100100000000 Ni=11101 verify=1
i=28 Si=110111101 Mi=11101011000100101101001011000110000101000011011111010110001100011010011111100111000000000010001001100011001111000100001000101000011111000011000001010111110111111001101010010101000100110001100111100010000100010100001111100001100000101011111011111100110101010111111010111101011010101001110010100010011100001010000001110110101110000010100010100101000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001110101100010010110100101100011000010100001101111101011000110001101001111110011100000000001000100110001100111100010000100010100001111100001100000101011111011111100110101001010100010011000110011110001000010001010000111110000110000010101111101111110011010101011111101011110101101010100111001010001001110000101000000111011010111000001010001010010100000000 Ni=110100 verify=1
i=29 Si=111000011 Mi=11010110111001101110000010010010010111001000110001001101111010101100100100001110101101100101001100101010100100100010100001001101000111110101101001010011111100000001101101010001001011110010110001000110011000111000011000001110110000101011001001110011101010100101000001111110000001111001110110110110011011110011101101010100111111011000011011100111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001101011011100110111000001001001001011100100011000100110111101010110010010000111010110110010100110010101010010010001010000100110100011111010110100101001111110000000110110101000100101111001011000100011001100011100001100000111011000010101100100111001110101010010100000111111000000111100111011011011001101111001110110101010011111101100001101110011100000000 Ni=1000101 verify=1
i=30 Si=111001111 Mi=11010001001110101001100010101101111111000001011011111001011100111110101100010110000000011001000010011111010111101000101001011100010001001001010001100101101010101101100010111110011000000011011101001000111111000001110101001101011000011000110100001111000111010101010101010011010111001011111010001111110101101011110011110010110101001110001011001011000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001101000100111010100110001010110111111100000101101111100101110011111010110001011000000001100100001001111101011110100010100101110001000100100101000110010110101010110110001011111001100000001101110100100011111100000111010100110101100001100011010000111100011101010101010101001101011100101111101000111111010110101111001111001011010100111000101100101100000000 Ni=1011000 verify=1
i=31 Si=111010111 Mi=11011110001111101010110111011000101011100011000111101001010011000000011001011111010011110101000110001011011010001100010110110100011000101101101000110001011011010001100010110110100011000101101101000110001011011010001100010110110100011000101101101000110001000000100000011111100000011000000000110001011110110110010000010100010101111111100010110011000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001101111000111110101011011101100010101110001100011110100101001100000001100101111101001111010100011000101101101000110001011011010001100010110110100011000101101101000110001011011010001100010110110100011000101101101000110001011011010001100010110110100011000100000010000001111110000001100000000011000101111011011001000001010001010111111110001011001100000000 Ni=1001101 verify=1
i=32 Si=111011101 Mi=11011010000111011100111110001111001110001100101001001100010101111110000100111110000001110011000100111111110110010011001010110011110010000011100011000001000100001010011100101101100010011111111011001001100101011001111001000001110001100000100010000101001110001101100001110100011010010101001011011101011001101001011010011111100001100101010111000101000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001101101000011101110011111000111100111000110010100100110001010111111000010011111000000111001100010011111111011001001100101011001111001000001110001100000100010000101001110010110110001001111111101100100110010101100111100100000111000110000010001000010100111000110110000111010001101001010100101101110101100110100101101001111110000110010101011100010100000000 Ni=11001101 verify=1
i=33 Si=111100111 Mi=11000010101111001110000111011011010011101111100110011001110111001110001100010101011100101111001101000000101010000111001011011111111011101010011110110110011001001110111100111000111100001011000110000110101100101011100000111111000100101110110000000110011111001001111000101100011001011001111110111111110010010110001011000011001111110010001011000011000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001100001010111100111000011101101101001110111110011001100111011100111000110001010101110010111100110100000010101000011100101101111111101110101001111011011001100100111011110011100011110000101100011000011010110010101110000011111100010010111011000000011001111100100111100010110001100101100111111011111111001001011000101100001100111111001000101100001100000000 Ni=10000010 verify=1
i=34 Si=111110011 Mi=11001010010111111110110101110110100110000011011101010101010000001001010100010001110111110000011101110110111000011011111001010001000000101001000011101110110111000011011111001010001000000101001000011101110110111000011011111001010001000000101001000011101110101110010001100000111100100110110001111000000110011100010010011010110011110011001110010111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001100101001011111111011010111011010011000001101110101010101000000100101010001000111011111000001110111011011100001101111100101000100000010100100001110111011011100001101111100101000100000010100100001110111011011100001101111100101000100000010100100001110111010111001000110000011110010011011000111100000011001110001001001101011001111001100111001011100000000 Ni=1010000 verify=1
i=35 Si=111110101 Mi=11001001101010010100001001001101110100111100011000011011011111001001110110101010001010000010001100100001011111010010010001001101101010111101100000100101110001011001011010011110011001110011111111011110000001010011000010001111100101011000111000011101101100101100100010100011001001010010001010011101011000101011110001011100001110101101110001101101000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001100100110101001010000100100110111010011110001100001101101111100100111011010101000101000001000110010000101111101001001000100110110101011110110000010010111000101100101101001111001100111001111111101111000000101001100001000111110010101100011100001110110110010110010001010001100100101001000101001110101100010101111000101110000111010110111000110110100000000 Ni=10111101 verify=1
i=36 Si=111111001 Mi=11001110011011000110100111001011011110011010100101000010000000011011011101101000100001000111100101100000010100010011110101010110101001110110100101111000001001001010010001100111110010110000001010001001111010101011010100111011010010111100000100100101001000101010001010000000110001111101100110100110111110110101111001011101011001111111100000010001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001100111001101100011010011100101101111001101010010100001000000001101101110110100010000100011110010110000001010001001111010101011010100111011010010111100000100100101001000110011111001011000000101000100111101010101101010011101101001011110000010010010100100010101000101000000011000111110110011010011011111011010111100101110101100111111110000001000100000000 Ni=11101101 verify=1
i=37 Si=1000000011 Mi=1000100110011010010101001010000010100011111111101110110100101000100111000100001100110001100111011101001100111010101001111111010000001110000010010000110110001011010011101110100110011101010100111111101000000111000001001000011011000101101001110111010011001111101110101100100110101010110000110000010010011111000010011110101101011111110100101001110110111010011001110101010011111110100000011100000100100001101100010110100111011101001100111010101001111111010000001110000010010000110110001011010011101110100110011101010000101100100101001101100100001001001010111010011110101101000111011101001000011001101100110000001110000010010000110110001011010011101110100110011101010100111111101000000111000001001000011011000101101001110111010011001110101010011111110100000011100000100100101111111011011101101111000001101101011010110001000001010011010010001110010110000010011100000000 Ni=10110111 verify=1
i=38 Si=1000010001 Mi=1000110101111010011011011000010010110100111100010001110011011011100100011101011100000000101100010101001000111000110110101011100010011000100010000000010000100011000010011100101010110000110111101001101110010001010000101011010011111101100100100101101111110011011100001001001011011000000100000010111101110101110011011110111111001000100000101111000010010101111001011101110000001110011101001001111010111010100010010000110011100001011110110110011010000111011110000111111111000001111011111000101110011001000001001010011001110010000001110011110111001100001000010000000101010011010101010100000110001110000100011110111010000011010110110111011000001011010111110101010100000010100101011110010111011100000011100111010010011110101110101000100100001100111000010111101101100110100001010100110110010110011101111111110101011000010111010111011111001001001011111010111111100100000000 Ni=101110110 verify=1
i=39 Si=1000010111 Mi=1000110011100011010011011100000011110101110001100111011010100110101011010101101011000111001001110100000001100011100010010001011100001010110011000101000001011010000100111010000000110001110001001000101110000101011001100010100000101101000010011101000000011001111110111000001101011001001100101111111110011010011010011010010101010110110001001010110010101111110110010100110100011001011011000110000110011110100110000010010101010111111011001010011010001100101101100011000011001111010011000001001010101011111101100101001001011111100111011000001111100110010011011000010110111000101101100111001100010110101000111100001010110011000101000001011010000100111010000000110001110001001000101110000101011001100010100000101101000010011101000000011000111000100100010111000010101100110001110011011000101100000011010000000011001011010100010110001011001100110101111110100111001100000000 Ni=110100110 verify=1
i=40 Si=1000011011 Mi=1000111111011110101111010010000001100001110101000010001100010101010000000111001101001110100100111000100000101101111000111000000001000011011101001011100111001100011110000110011011111001101011101011011010000011110100111110101011100011000001101010101000000110001111101000000111001111110101010110011101101011111101110000111010000110110010100111001101110101101101000001111010011111010101110001100000110101010100000011100100001001111001011010110010101101001001100001110110001001001000000011000101100111011100101001010000111101100101111011100011111100001101010100100101011011001001010100100110100100011000101010010101001000100010101011000010101111001111011011100001000111010000111111001001010000101111111110000010010110001101000101110111101011111011101101010001001101001101001111111111011101101001111010111011111001100111000111001011011010100010111111101101111100000000 Ni=110000000 verify=1
i=41 Si=1000100001 Mi=1000000100000111111111111101110001111010100110000010001010001010110010010110001111011111001010011000110000000110011001010110010011111101101001001001101111110010110101000010100010011101100101111011000011010101001110010000110001000010000000010001000110010000110101111011111000111011000100000010110011000011100000001010110011011010111000011100101000101110111110001111001101001101011100011010001011111110100101100010100110001100000001100110010101100100111111011010010010011011111100101101010000101000100111011001011010110010110110101100011010110100101101110011000101010100100001000100011101110110011110101111101111000001111111110000111101110000101100110110111101000011100110000100100010101110101111001001011100111000000111011101001111010100101000000101010101111101011010100011001101110010100111111100101000001001101011011011111111101101101011100111010100100100000000 Ni=101001011 verify=1
i=42 Si=1000101101 Mi=1000001000111001000110001000100110111001110110010100001110100001001001001001000101101010010110011110011011001001010001110100010001111100111110111101100010110100101010110001111000101001011101001100110000001110110011010001100101001111111110000110101111110011111111001001001000000010100110110000000110000100010001101011100100011010010101110000111100111111111000011010111111001011111000111000000011001110001000011100100011011011000001111110110101001101110101110110111000110000101100001111010100010101101011011110010111100010001100001011011100100111100111010100110000010110011111111000011110001000110111010001100001011000011110101000101011010110111100100111001100100001010000110001101001110111011111110100100010011110111001110101010100000100110101011100101011110100000000000010011111100001101000000110111011110010010000110010101100010010010000101100011011010100000000 Ni=110101110 verify=1
i=43 Si=1000110011 Mi=1000010111100001000010101010111000111000011011010000111110111101011111110101111010111100111111100001000010010101001001001101110110000111000011000010100111101100101101000000111010010100001111000000001000110001101111110110110101100110100010010001010001111011001111100001111000000110111000000011010011011100010011011011101101001001000101101110001011000000101011110111010000101101100011111100101011010100010110010010111000101010110001011101010011010101010000011111000110011100011101101001000001011111011111001110101001111001101111010101101100100001000011110001100000001101110111100110010100001101100110000111100100011100101111001100100001101001100010011001100000010101111011101000010110110001111110010101101010001011001001011100010101011000101110101001101010101000001111000010010000001010111110001011001100001110001010010101000010111010000101001011010101011100000000 Ni=100101011 verify=1
i=44 Si=1001001011 Mi=1001100011111111100011000010000011111111100000101111101110101110001001011000000000010001010000000110110001100111001011011011101011010110001000011000011110101111001000000011011000110011100101101101110101101011000100001100001111010111100100000001101100011000111110101001000110101101110010011001111011101110001111110101000111000111111001011001010111011010000111001111111010101110100100011010101010000101011111011000010111101101000011100111111101010111010010001101010101000010101111101100001011110110100001110011111010011010010110110111001011100000101000000110010010001100000111111101010011010101111100001011010110001000011000011110101111001000000011011000110011100101101101110101101011000100001100001111010111100100000001101100011001110010110110111010110101100010000110100001100100001100001100111110000011000111011001100011100000001001100110100011110100111100000000 Ni=100111000 verify=1
i=45 Si=1001011001 Mi=1001110000001000011010000000101101001000110101111001011101110000110001010110000101000100001000110110101000001100110010100101010001010011100010101110010101100000001101111000100010110101100100100101100110110001101001111000000111110110010110111110000101010100110101111101111110011001111001000110101110101010101001110111110001100001101011000010010101101000010111000011100000111010011010101001100011110110110011111101110111001110011000011000101111001101000110010000000010010100001111001001101110001110010001001000010111010011111010100100000110100011100101111100101000000100110010000100111110110000001110000101110100010000010000110101110110000100011111111100011000001010001110110100001011100001110000011101001101010100110001111011011001111110111011100111001100001100010111000001100011101001101001001000110011000111100000100010111111100111001100101101101011000100000000 Ni=1010 verify=1
i=46 Si=1001011111 Mi=1001110110010111011110001101010000110010010100101011101001010001000101010111010010010000000011010110001111111010100111111001111000100000111010001011110100100000011111010000010100010011000010011100111000111011000001000011100001111001101010001101001010010011010100110100110010110101111111111010111100011000110000010110011100011100100011101110001011111100111100010000011101000101111010010000001111101000001010001001100001001110011100011101100000100001110000111100110101000110100101001001001101000011000100100010001110000101011100110001110000000110010011010001011001001010101101010001101101011110101100111100110001101101111001001111010110101010100001000111001010100101101100010110100011110111111111000110010010111111011101101001110111001000110000000010010101101110000011101010101101101111001010010101001110110100110110100100001001111110111011110010001001101100000000 Ni=100111010 verify=1
i=47 Si=1001100101 Mi=1001001101100010000101010000111111001110010110011101010000110100100010100010011010110000000011011111110101111100000001101011001101100101100100101001011111100110100001101111111010111110000000110101100110110010110010010100101111110011010000110111111101011110001001110110100011110011011110110011100101001010000010011101011010111011110011011011011001110111010010001010101011110001101101100001010011110010111011111010011000111011101001000101010101111000110110110000101001111001011101111101001100011101110100100010101110011010101010011010111100100011001001110101101000100110100000000000000100010011010101101101100101100100101001011111100110100001101111111010111110000000110101100110110010110010010100101111110011010000110111111101011111000000011010110011011001011001001010110011001111100000001110111101010011011001010100101100101111111110101111000010010111110100000000 Ni=11100100 verify=1
i=48 Si=1001101001 Mi=1001000001010001010100010000001010100110011011010001110000001100010110010110001000001011110110001001010111111101011100100001001000100111000111011001001111000010100100000000100110001011001111010001100001100111001110111011111100110110111100011001010101100100111000010110000100000011011010110110010011101011110001110000100001101111101001010001001111101100000001101010011101010001110010100010101001010011001100000101011011000100101011111110101110010000100100010011100011101100100111100001010010000000010011000101100011001000011000011001101111011000101101010110110110110100101100111001110011001010000010101011101001011010101110110110101111011100110010001101000000101111101001111100100101111001111110111101010101000011111011010011011111000000111100101100011011001101001001101001011111001101101100100000100111001010000111001001010100100100010011000001000000000100000000 Ni=100101011 verify=1
i=49 Si=1001101111 Mi=1001000111001111100000101110000110101000000000001111111000010101101011010111110111111100011101100101011100011100100000011110011111000000101111110111101100001101110000111110100111001100110101111100100100101100000100010100001000001110000011000110100010110011000000100100110110101110000000011000101110100000011000100001101111001010010111100011011001011111101111011000011011100001111101001110011001101011111001001001011000001000101000010000011100000110001101000101100100010000111010010101010111100001011011011101000111101100100001110100110110010001101101110101100001110101111101001010101111100110010010110110011000100111011111111100010001110110110011100010101000100101000110110001111011100101001111010101001101001100000000100110010011011010100100111111001101111001011010110101111001000100001101000010100000000000001101101001001100101011000101010101101110101100000000 Ni=101110011 verify=1
i=50 Si=1001110111 Mi=1001011110010011101011001100111000110010101010001001111110101110010110010010100001110101110110000100101101111011001111010100111000100010000001111011101000100100100000111001001010010001010011000101111000011111110101101001111000111000000101110001100011110010100100111000011111110010101110110011101111010001111011111101100110100100111010010001001000100001010001011010111001111110011001000111010011010110000000010011111000001100001101100101110101011101110000101100010011011111111100010101111110111110110111001011001001100100110000110110001011001001011010011111100001100100000110100101111000111010110101010010001110100110101100000000100111110000011000011011001011101010111011100001011000100110111111111000101011111101111101101110010110011010010111110010000111011010101010100011101100000100011010010000111110101001111100111000101000100000111001101001001001001100000000 Ni=1011001 verify=1
i=51 Si=1001111101 Mi=1001010100111110110110100101001101010100001110110110101011011000110011010100111100111011001111100100010001010110110111010011110110010100110000101000001000111000110111100111000010000111111011111110101100000111001111001010111111001100011001101110000000110101111110110100111101100010001101010101011001011011001000010000100100001010001011010100100010100101010110010000001011101011100110101011101111011101101000000001001110110000111011100100110110001110101010100001101101010011100101111000111110010001000101011011011001100101000110001000010000000110001001100100000101001001100100000110000101100100101101111011001110100011010111101010001111000011001001001011000101001000110001000001100000011110100001001010001011111000001010100101010110010000001011101011100110101011101111111000111011111010010100100100001110110100001101010100000111000010100000000000010110010100000000 Ni=100101010 verify=1
i=52 Si=1010000111 Mi=1010000011010010101100010001000110001011101110110011000001100011011011110100011010011100111001100100101100110101101011111101001101001111100100111001101110000001000000110101000001001010011000110100010100100100110011000011110100011110001001000110011101001001001001000100000011010010001010011010000000100001110111001101101110101010101000000001001011101100010101110001011101101000000011111110110011111100011000100001001111001110001110111011111010110000101000011100001000101100011111011100101000110110111111111001100001101101011100111101110101101110001010010011100000001110110000101101001111001100000100000100000110000010111110000110111101010010111001111011011010101010001000111001000100110110010101001110110001010111000101110110100000001111111011001111110001100010000100010100110101110001011110101111011010001111001011101110110111110000011101110010110010001100000000 Ni=110110101 verify=1
i=53 Si=1010010101 Mi=1010010001110010111101011000001101011000111011010111011011101000111111011001111110110010101100010110101111001111111110011010100011111101001001001100111000001001000110000110011001011011101011001101111010000111100101010000101001010110100101110001101110000110011100100111111111001011010001001000101111101111010111011110010100010100001010110110011111011100100101100100010010100111110101110011000001100011001001110010111101101000001011101001100010011110000000111110000101100001001101101111111011000101101011110011111010101110010001100001111110010101100010011111111010001100010010001001010110001100000111110111110010000011101101101010100100001101100101000101010101110110011110101011000111000100010111111000111101111101110111001001011001000100101001111101011100110000011000011011011011100100101111100010001111111011001010111101100001000010100101110100100000110100000000 Ni=10110 verify=1
i=54 Si=1010011001 Mi=1010011101111101110100001100001111010110101000000011000110000001100010000011101011000011101011011111001000101010011100111000100111011011101100100000000101011001010101101111100100010101001110011100010011101101110110010000000010101100101010110111110010001011110100100001100111010111011010110010110100010110001101101011110101010101001110111111011001100000100100100001010011001100001110010110100001000110101001011000101000110000010010010000101001100110000111001011010000100011010100101100010100011000001001001000010001111101111101011111101110010110000001000010001011101111000100010101001011101100000000000111011011101100100000000101011001010101101111100100010101001110011100010011101101110110010000000010101100101010110111110010001010100111001110001001110110111011001000101000100001100010001011001001111000001001000111001000100011011011101100001110000111000100000000 Ni=100000000 verify=1
i=55 Si=1010100011 Mi=1010100101100101111101100011111101010010010000110110000001111010010101110100101111111101100011000000100010101101011100001111100101000001100111110111100100010000101111000010101000011000101100110001110001000111111000101001110101010010010011001000001001111011001011011010011010110100000101100100110010011101101111100111111100111101000101010010001100100001110110100001001010010111011101100010011011100011011110111001100110100110101100100101100011001010101011101011110101101110100101011111111100111100011110110011101010110010110111111010010010101010011001101000010100001101011000110111101011110111101111100111001110010110100100001110110100001001010010111011101100010011011100011011110111001100110100110101100100101100011001010101011101011110101101110100101011111111100111001001100000001010001010001111011101101101011001111110000011101000101110111110010000011100000000 Ni=111100110 verify=1
i=56 Si=1010100101 Mi=1010100011100101100000101001011011100011010110000110110111111110010100101001000000110101010000001000101100101011100111000011101100011101001011010100101000010101001111000010111101100110101110110100110011000011000100100000111001100100100101111110001010110010101011111011000111010100100100100111000011110011100110000001110010011001101011001101000010001010011011000010010101011011011100000100111110101000000001010001111011100101100000011011010110001011100010000100000010001011001010111001110000111011000111010010110000011011110111100011100100000010101000000000101110010111001111111011011100101110000011100001011011110100111001001100011000001100111010111110010100100010011010010011101110111110111100011111101000100011100011010101111001101110101010100010100110110000100101111100111001010111001101001111101110011001000110100010000111111111100111000110111011110100000000 Ni=1001001 verify=1
i=57 Si=1010101111 Mi=1010101001101001110001111110111100011111110101000111000011101100000101100001111001111111010101110011000101001000111010101111001000000110110011001111001101000100001100011110100110010100011111110110111011101011101100001111101111010110001000110000101010110111110000101000100001100101100011010100011111101001011110101011101101011110011010101000110100011011100100101011001110011101101011111000000100010010010000100101110001100100010111010010011010100000001111000111000001110010111101110000110100111000100110000000010001011111001001111110010010011111000001011011010100011110111001100111100011001010101100010110101111100000010001001001000010010111000110010001011101001001101010000000111100011100000111001011110111000011010011100010011000000001010000101111110100011010110100101110011100100000011000000111001111101010011011000101000001000001001110001100110010101100000000 Ni=100000011 verify=1
i=58 Si=1010110111 Mi=1010110001000011000011001101001001100001111100100011111001100011010010000010011110001111001000010010000011001001100010001011110010010010111110000011100000010001110111100001101011100011100101011111101000000011110100101000001001101000010111001101010110000001000010110001100110010000010101100010111100111011100011110110010000110001100110110111011101010000111010100011010010001001010101011101001111001100000101100111101100011110001100110010110001010001000000110111010110111101011110111011100100001100001111111011010110000010010011000100001110011010001110010100000010010001010101110001110111001010011101000010010101010111010011110011000001011001111011000111100011001100101100010100010000001101110101101111010111101110111001000011000011111110110100110110101100101001011010100100101011100110101000001111111111000001111111101110110000100100101111001100010101001100000000 Ni=110000011 verify=1
i=59 Si=1010111101 Mi=1010111011001111101010000011010101011110110011001010011110010000000010101110100111111100110111000000011110111010100110010000001000110011111010101100000110010101000011111101000010101111110001000001110001111100000100110000100100100001000011010100011011011001100110000110110110001010001110010011100001000010111100100000001110001110111000100010000010010011010110111110111111101101011110110000110000001101111000110100010100000101100010010111001111000011101001101110010100010001001110101100101111001100110100111101011001001000110000100100111000100101010001000101000111111011001000101000001110100100111110000101011010101001001101011011111011111110110101111011000011000000110111100011010001010000010110001001011100111100001110100110111001010001000100111010110010111100110011111000011001001111111101010000010010011111110011010000001011001011011010111000111010010100000000 Ni=1001101 verify=1
i=60 Si=1011001111 Mi=1011000000011010101100011101111110111011010010100110100111010101000000010110001101111011010101101110110100010011010010101010111001000101000111010011011001000000110010010110110000111011000110011001011100001100001011000100100011111110111000110110111110100101010000100000000101110011110100000110100000111101101010001100000001110010101111101011100101101101010011100000111100001001111110000001001010000101001100111001010010010011000101111110101111100010101000000011100111110011101110100011000111000100001101010110010000011001101101010011111011111010110100010010100111011100000110010111000110011011000010011000000100101000010100110011100101001001001100010111111010111110001010100000001110011111001110111010001100011100010000110101011001010111100110000000010111010100010110001011101110111010001111000100100111011000111101100101010110011011001000101101011100101100000000 Ni=110111000 verify=1
i=61 Si=1011010001 Mi=1011011110101111101100110011010110111100100001111000001111101010010110101001110001101001001001001000011101000001111010001000000001011110101001110101011001000001010101011100111011110010001001011111110111011100101100011000010100001001100111001001111011010111110011011110001101010010010110101010001010100001110011010000101100110110010101001001110001011000110000101000010011001110010011110110101101010001010111100001101000011000111011011101011101100101011011111100000110110110001001110000100011100110000000111000111011001000101101000110100110010010001101010101011010111111110011010010001001110010111011100010001110011000000011100011111010011111101011000011111111100101001100010110011011100000011001100101110100101000111100011010101001011010001101111011111001111100010001110001101110011000000000111110001100000100000101100101010011100100010010010101010011100100000000 Ni=10000100 verify=1
i=62 Si=1011011011 Mi=1011010100101010101110101110000100100011101101101001101000011001110100101000010101010100100011100101111010001101011000010011011111000100101011110001100101000010001100000111101111110101101010110010011001000111011100001011010000011011000000100100000001110001011000011010101100100000101100010111001100101001110001001101100001001100101000110111000011001110100100010110001111001000010100011111001111010100010100110000110001000001000011111100000101010000001100111111101110101010010110011000110111011110110100101001001011110110000010000111100011111100100000100000001000000010100010001100000010111101100011011010010001011000111100100001010001111100111101010001010011000011000100000100001111110000010101000000110011111110111010101001011001100011011101111011010010100100111001011100001111101001101001000011010111010101000101111100011010111110001001111101110001111100000000 Ni=10100101 verify=1
i=63 Si=1011110101 Mi=1011111000101000101100101010000100110001000011000100111011110011100010011101100001010111010001101000001010001011000111101100000011000011011110101101111111011111011010110010010101011010100100110111000110011011001110001001011110111011011101000011100101001010000101011010010100000110001011100011010000001000000011111111111000010100011101111010101011110011101001000110100000101000101100011110110000001100001101111010110111111101111101101011001001010101101010010011011100011001101100111000100101111011101101110100001011101000111001111111101000000100010101001101110111111100111011100011001000100000110100101111110101000010111111000010101001100000110101011111001100010000001001100101011101111000000011101110011010010100000000101101000100111001111111110010011110001011101010000111011000011110011110011011100111110001111110011011000110111000011110110101110110110100000000 Ni=111010010 verify=1
i=64 Si=1011111001 Mi=1011110100101001101111111111111000000101101101011101111001100101000110101110100100110011011111000111101001110010101101100001010101011100011011001001110111000011011100100000000101101110111101110101011001110101110100000010011010101001010100000111110100010101111111111011001100011111011100000100000101011111001011111100010100100000001110010111000111001110000011010111111101111110000100001110011110110001110001000001010000110010100110111100101110110110101000100010011111000111101001110010101101100001010101011100011110110011100011110100100011011100000111011000010011001001101011010110100011010000000011000110110111110011001101000010010001110100101111101101000111111111001001011010110100110010001011001011000000011101100110001100111111010100111100111000001101011111110111010111000010011111000100111000100100010011110110111101111101100110100001100000110001000100000000 Ni=1111000 verify=1
i=65 Si=1100000001 Mi=1111000111001010101110110000001010011100011111001001110010101001101001111000001100011100110100110100111011000101101111001001010001110011110100010100111100111010111010011010011101100010110111100100101000111001111010001010011110011101011101001101001110110000100011001011000001101010111100010110101100110111100000110011101010010111101100011010101100101000111001111010001010011110011101011101001101001110110001011011110010010100011100111101000101001111001110101110100110100111011000101101111001001010001110011110100101000100000010000000001011010110100010011001011000011100010011111011101101010101111101110001110011110100010100111100111010111010011010011101100010110111100100101000111001111010001010011110011101011101001101001110110001011011110010010100011100111101000101110011010010000100011101100111110001011100000101101101000100111000000101000111010110100100000000 Ni=110100101 verify=1
i=66 Si=1100010011 Mi=1111010001010010101101101111100000011010100010100101111000100010000000101111100111101110011010110000010011000000110001001111111001011101000100100000110110111011001010101011001110100101100100101000101011101111010000110101000001010011010000001011100111001100011011010001011000110010000001010000111010111001010110111000100001110100100011111110000110100110011110110001010000101010010010011100001000100011110010000100101111011111011100100110111111000100000001000011101010100011010011110001111110110110100100011001100011111110100100100111010110010101100110010000011110111111010101111111110010000111100101001110000011100101001010110100011101101010111100000000111110100110011110110001010000101010010010011100001000100011110010000100101111011111011100100110111111000100000001111110101111101001100101001111111111011100101110001110000110011110001111001111111111011100000000 Ni=111010000 verify=1
i=67 Si=1100010101 Mi=1111010110110010001101011111111100110010010000100110110000101000001110011101111101010000110100101001000010110111000010010110100111001110000011011010000011100100111010001011111101101100000010111000101100001101010110110111111100101111001000001001100100100100101101111100011110011010111000100000001000001000111100100100111011110111111100011101110101100100011011101110100101001000010110111000010010110100111001110000011011010000011100100111010001011111101101100000010111000101100001101010110110111111100101111001000110100111111101101100010110101111100111000000101011101011000101100110011010110001111000111000001010011111000011101011010100010000001100010101111101001101100111100000001000011001010110001001000101000000001111101110011011110001111001111111110101001011101101100011110101100010010011110010111010100010001001010111111001010110110111000101111000110100000000 Ni=110010 verify=1
i=68 Si=1100011111 Mi=1111011110011011011001100100100010001111000101001100101101010111000110110000011010100111110010111000110111110000110010000110101110101100101001111110110111101111111110101000100011010000100101011111011100000100110100110111001110101011011010110101010100110001000110010011100010100110110011101001011111110011101110100111010100010000011011110100010111010111101000001101100011000000001111100110010111000110111110000110010000110101110101100101001111110110111101111111110101000100011010000100101011111011100000100110100001010110111000110111100100111011100001100101001010010001100110110001100111001001101000101000000101110110011100101010000111010010011110010001001001000111011101111000000110001111111001011011101000110011111010011100010100011110001110000101101001010000000100110111010111111111010110110000100100101011110011011001000001011010101010100001101101101100000000 Ni=11011 verify=1
i=69 Si=1100100011 Mi=1111101110110011100111111010011110010100000111011100001011010110101001011101001001110101110001010101110000100000001000111111011001001110111110111101001000010011110001000100001110010010010101000010100011011110011001011111000000001111010101101110001011010101010100000110000001100001010100000110111100100010011101100111011110100101111100110001011011101100011010001001100110001001011011011111100011110010110001010101110000100000001000111111011001001110111110111101001000010011110001000100001110010010010101000010100100101001000000101100111101000000011111101101100101010001000010100100110011111010111101001100110110100001101100111001110100000010110010100000101011000010111101110101000101001001101001011100110101010100110111011011000001001000101110100111111100100011000000001100111000011000111001101111110111100001110101010110110101111111001000001010101000011100000000 Ni=1011000 verify=1
i=70 Si=1100110001 Mi=1111111000101101001101010010101000100110011100100100001011001111011100101110000111011111011001000110010110000100110011110100111000100111100110110011101010111101101100000110100101001100000001000100011110111001000001110111010110001011110001010001001000101101001010101000010111011011110111000100101101100001101010111001101101000011001100010011100011010100111111000110110100001011101111010100000011001100100011001011000010011001111010011100010011110011011001110101011110110110000011010010100110000000100010001111011011011100101101001101101100101100111011101010000100011111010001010001001111110010101111100011100001101110110010010010101001000010000111111111010111110011100101111111001001110110101110011111011111010000010010110111000111001100011111000001010101011001010111101110001000010111011100000111100111000011010101101000011010011100101111000010111101100100000000 Ni=111110111 verify=1
i=71 Si=1100111011 Mi=1111110000000110011100101011111001101011111010001110110000101100000011000000110101100000010000101001100010101110100101000100111010001010000110111110111111000110010011001010010111100001000010011010100000010110111010101000111001000100000110100000101010010001111010010111001100110010010011111010010100000011101000110010001001110101100010100010001101010001110010001000001101000001010100100000001000101111111110101110011001101110010110100100111101101111010011011011001000011100011110101001111100111011110011010011100000011010110011111110000111010001100010010011001111101001111101111001101110101001001110011010100111110011101111001101001110011110001011000011000001001010110101011110111000100011000110101111100000111011001111111001001011001100001011100001111110110000001100000111000001100000100111110110111011011001001011100011111000000110100000010001000111111100000000 Ni=100101 verify=1
i=72 Si=1101001001 Mi=1110010000100001001000101110111001100001000100111001000111111101000011010000001011111011011100110001101100000001001111010111100001100001000110101101011101101101001110011000110110000000100111101011110000110000100011010110101110110110100111001100011011000001100001110001110001011101100110100111011111111100011011011001100101111010001000100101100111101010000101010101100010010111010101111111001110000101101111010000110111110101000010101010110001001011101010111111100111000010110111101000011011111010100001010101011111101101100101111011100100111101101011010110010001011110101110001011000100010111000111000001100001000110101101011101101101001110011000110110000000100111101011110000110000100011010110101110110110100111001100011011000000010011110101111000011000010001101011101110011001010111000100110110000110001101101001011000010011111100111000101011000010000100000000 Ni=111010100 verify=1
i=73 Si=1101001111 Mi=1110010111000111100001000000000001101010010001001111010011101100011010110110111000110000110001000010110110111110001111000011011110110010111011111111101001100100111000001000001011100001010101110100010101100111101000010001100010011000111011011000010010001001011110100010000101101000000111011000111011001010111001111001111100100101010000110011000001001110000010000010111000010101011101000101011001111010000100011000100110001110110110000100100010001011000110101110011000000001110101011010010000110000111001000111111011110010011110100001010001100101111000011010111100111000011010111110110010000010001101011000110010100110101001001101101000110110011001110100101111001010100000001001111110111011000101000100101100100000010100101000011111001001001010111101011111011010110111110010001001001101101010001011111010101010010100100100100111001000000101110111100100101100000000 Ni=110110011 verify=1
i=74 Si=1101011011 Mi=1110000110101111100011111100101110101101111000100011111001100111110010001000110001111000011010100100100111010100011111010101101000001011111111101001011010111001010000110001100111111100111100001001011101100100101001101111101101101001111100100001111110111001101100110101000111110000101110000100111101101100011010001000100101110111101011110101110011100010011110111111000001111001100101100101011110110001111010001011011001110001110100110000101011001101100000011010101010011100100110100011000001000010001010101110101000100000000101111111100011111101000100100001000000000001100101011001101011100110011001100110110111010000101100010000011001000100100000001001100110001011100010011110111111000001111001100101100101011110110001111010001011011001110001110100110000101011001101011000000000010100010011010100011001110110100000000101001000110000101011110001001001111100000000 Ni=101110001 verify=1
i=75 Si=1101100001 Mi=1110110001001000110111101111111000001001001010101111000010011110011110100111100010100001100010010101001010011101110011010001100000001001001000110111000011001001011010100110101101001111001000010011100000010101010110000011000111010101111100101111000001011010100001011111011001100100011110111001111010110010101010101000110001110100100000001010111000010110110101110101100111110110011000011110001100111001110100101110110000100000000111000111101101000001000111001001100010011011000101000111110001011111110011001101111001100101101000110000010010111100110010010111100101101011111000010000000100011111110010000000100011100100110001001101100010100011111000101111111001100110111111011110100110010101110010100000011011011001011001000101011011101111101011110111010001011000110100011011111011011001011011110110011110100001011011111111100100000000000000111111100000100100000000 Ni=1011010 verify=1
i=76 Si=1101101011 Mi=1110111001101000010111110111001111100111111110101010101111000100100010010111111001111101010101101110011100010010110001111101011101010100010000100000110001011001001110010101010110000001101100110101000011001011100011100110110100010111100011011110101001101000010000101101111101100000101000001000100110010001010100110000000010010000110010001101010001110101101001011111111101000001011010101111100010101110010010010101101110011100010010110001111101011101010100010000100000110001011001001110010101010110000001101100110010011111111111101000011101010011100100011100001011111110001011110110101011000011100000111011000011010111101101011001110110001000101000000101010010100011110100111101110111000000001110000111011111100001001111100101101101111101100101001001101110100100001111110100011111000010011101111011101000111010000101011110111001111000110111010101011110111100000000 Ni=101000101 verify=1
i=77 Si=1101101101 Mi=1110111110001111010100001111100011001111011000111001010101010001100001101010110011010000110011011100101011001011111010111000011110010001000101100110011101010101001111111110100000000111000000010010000001101100000101101000011101110001001100100110101011010110001100000001100010000000101111011110010001010110110111001110000001010101111001001001100101110010101100101111101011100001111001000100010110011001110101010100111111111010000000011100000001001000000110110000010110100001110111000100110010011010101101011111101000011110100101101111001011101111001110101011101010111010011101010010001000010111100110111101001001001110110110100110110111010110110011110110101000110111110010110000101110100011100111001001010010110111101110110001100110100101010111011111110011000000101010111000000100110101011000001110111110011111001100101010110111100111001001101101101111010100000000 Ni=10000100 verify=1
i=78 Si=1101110011 Mi=1110100111000000001110110101011011001001100001100010101000101100001010000100001001110011001000011110100101001100100110001111110111110110000101000101110010001010010111010100011001010000101111100010010010001101011011010111000110110001011011101110100110101011010011011000000110111010101000000110101101111000011001110001000110101100010110001111100100011011000101101110111010011010101010011110000000011100110000001101111110000111010000110011010010011111110011011100000111110101100011000100011101111010101101010010000100010000110001111110101000011110010011111111010100001010011000000001110100110110000100001011000110001000111011110101011010100100000110000110100011110011100101100111101110011111001010111100011100001001101101100101111011011110010010110100111011001100111010000101100110001000111001000000101101111110001110101101100111100111110010010001110001011100000000 Ni=11010000 verify=1
i=79 Si=1101111111 Mi=1110101000000111001011010001111001101010111100101100110011111000101101010001001001101001010011101111000111111100110100010100111000010100000001001011100000100010111011101101010000111101110001100011100010110101111010101000100111100111010000011000000001110011001010000011101011101100010000011011110110100111011010111001101001011010110011110111010101110010000110011100110011011111000100011001001010010010011101111000111111100110100010100111000010100000001001011100000100010111011101101010000111101110001100011100010001111011010110100001010100000110110110011110011000001110000100001100111110010111001110011101111111110100011010101111101100011011011101010011011000001111100101000111011001000100000101100101100010101001010101011000010011001010110111101101101001100010010000110000011001100110111100111111100000010010110001111101010110001101010111001000000011101100000000 Ni=101110 verify=1
i=80 Si=1110000101 Mi=1101011000011011010011010011010101011001101011110011000111010110100001010001011111110010111000000010110111010001110101000110111001010100110110010001001110001000101010101101101111001110100101011110110000111110100000110000010011010100101101000010111010111001100100011101110001110111001110101011111011111001110001011011111111101100000010111001110101111100011010001000011100001010000110101111101110111000111001111001000010001100011111100110111111100000001011011101000111010100011011100101010011011001000100111000100100000110111011010101010011111111010111110110000011100000101010011101111010011011110010110111100001100110010010010100010110001100101001000001010110000001000000111011001110010011111001011001011111101011010110011010010011001111111110110110001010011101111100101111101001110001000111001011111010001000010111110101100100011000001001011010011001110100000000 Ni=10110001 verify=1
i=81 Si=1110001111 Mi=1101010000011010101110010101000001100011011100011011011010001100101101111101000101100111100110100000111101010100000001011010001110010100001100111011010010101010110110101000110100110001101111010011110000111000111100111000001010111101111001000110010000001001100011100110111011111011010110100000101011100000000011000110101010000001001100010101011010000010011001011011100010011111101011001100000000110110000101110011111011101001001110011001101101100111101100010000100101001110101111101000010100010111111001101011010001101010000010101111001101111100010100010110100111110110101001101000001001010000001001010110110011110110001000010010100111010111110100001010001011111100110101101011100001000111111100000011101110010010111100010101001101110111111111011011111001011101010010000100110101111011110000010001001110010010110111100110100010000010101111101110111000101100000000 Ni=111011010 verify=1
i=82 Si=1110100001 Mi=1101110100111000000100111110000101000100100001010010011010111001001111111111011111000110001010101111100010011100110110010010010100000011100101100011101110000111100101010111110001001110011011001001001010000001110010110001110111000011110010101011111000100110100011000011100101100111001001110000011111101011101010000010110101101100011101001010100011110101100000111111111011000010101110001010100010100101101110101001110101111010110000011111111101100001010111000101010001010010110111010100111010111101011000001111111000001010110111100000110111101011111001111010110100010011110000100000000000110111110110110100000011100101100011101110000111100101010111110001001110011011001001001010000001110010110001110111000011110010101011111000100111001101100100100101000000111001011000001100110010011001000110000100000111110100110111011011001011111000010011100000001100100100000000 Ni=110011001 verify=1
i=83 Si=1110110101 Mi=1101100100011011110011110101011000000110101001111001110001011000100110111011110010100010110011100101000000001101010110011101000010110010000010100101111000000010111111010100111000111010110000111101110001000000111000001111101001001001111010001000110010011001100101100001011001000101111010110011111111111010001101010011110101111010110000000110111101100111010000101100100000101001011110000000101111110101001110001110101100001111011100010000001110000011111010010010011110100010001100100110000010010000100001110110110010101110111111010100101010011010001111000111100111011100000110101101100011110010000011111111011111000101101001010011010110110010110111111100001100001001110111011110101111011010111011000000100010100011010011001100011110001101111001101000001100111100101110011100110101111101111110000010100010110010001001111000111000000100100001110000000010110100000000 Ni=100110100 verify=1
i=84 Si=1110111001 Mi=1101101011100000100100000111010001111101001001111000011101011000111010001101000100110001001011110101110010011010101000001010011110111001111000110001110100000011100011110010110101111111000011110100011001010001001010010011100000100100100010111011110000001001001110111001011010111011001100101011100100100011111010001001000100011101001101011010011100111101110011110001100011101000000111000111100101101011111110000111101000110010100010010100100111000001001001000101110111100000010001000111001010111100110111101101001110101110101001100001000111101110100111101111000100100101101010100110000011001111001010001100011011101100010110110101001010100110000101010101101110000100111110100101100110100111011011111011111101010001111111110110010001101000011101110101011101001101100001010110010000010010010011001011010000110000010100011101001111010111111100111100000101000100000000 Ni=1001 verify=1
i=85 Si=1111000111 Mi=1100000001001000100010011001100110110100110000100000111010011101111100110111010010000110111011000110010110001010110110101010100101101110011000010100111000101101000000010101011110000010110010011011101010110000110000011010100110100011000111110000100101000101000100011000011000001001011001000010011000110011111000001110001010110111000000000011011001011001001101110101011000011000001101010011010001100011111000010010100010010010001000101110001101001010111010011111011011111111101110110010101000111101001001110111000110111111000110010110011010011111100101001001000000110010100101011011010011111000101100010000001111111000100001110101101011001111110100010100001011111010111001010010000100011011110011011011001100111001001011101111100111010000110110000000011001101011111100010011101001101110101001000110001000010111111111111001001001001110001011100101010110001100000000 Ni=10001101 verify=1
i=86 Si=1111001011 Mi=1100001110111101100001011001000111110100011111010010010000011110000011011010000011111111100101101010111000000001100111010110001101000100010010000110110111000110010001100010000101111001101010001011101010100001110100000100000111001001100101111111110111010010111111000111010000010100010011101110000000001101110010110110000110000101000110000111110111101101101000010001111011110000011010111011001111001011001100000101100000011111101000111011100101010101101001110110101101111101011110101001001001111100001010010100000100011101001111100001000010011100110010001101000000110010011000001101011011001010100110111000000111111010001110111001010101011010011101101011011111010111101010010010011111000010100101000000100110100100010100011011101111110010000000101010011110100101110011111101011001000000010111001000110110110010011111100110100110110111110101001111001100111100000000 Ni=111001101 verify=1
i=87 Si=1111001101 Mi=1100001001000010010111010111011101000010100110100010000111001000010010110011101011010101101010001111101011111101000110010010010100111001100101000010100100000011111100100001111000001110010101101101111010010101011110001111011000001000001011000100010000100100011100100100001111000101111111001011000100000100101010100000100001001010010000110011100001010011100110010100001010010000001111110010000111100000111001010110110111101001010101111000111101100000100000101100010001000010010111110110110001110111111100010010001011000111100010100010001101100011010001100101110101110011101101100101110111111111100011000000010011011001011100010100010011101010101001011001000101101110110101000001101011010111001001111001101001111111110111010110011101100110111110000101111011110010110100100101010000001001101110101000111001011100011110010100000100001111110010110010010101010100000000 Ni=100110000 verify=1
i=88 Si=1111010101 Mi=1100010110000011100011010000111100011010111111011001111010000111100000000111110010000000010010011101100011011011001100000100001111011001010010101111101101001101001011011010101000011000100011010111101111100001101110101110111011011111110001010011001011110000000011110101111011111100011100100011110000010001110111110101111010011101101111000101011000010000111101100101001010111110110100110100101101101010100001100010001101011110111110000110111010111011101101111111000101001100101111000110000100010110011110011001101010001001011111011010001010001010010100101010101001101000101011111101000100000000001101110000011010001111110010011011110010101001111100111111111011100001011100100000101101011000101111110100001010000000011001000111001011000011101111010011100000111000111100110000001110011100110111001010010010000010111111110101100000011001110101110001010100110100000000 Ni=1010011 verify=1
i=89 Si=1111011001 Mi=1100011001110110000110011101101100111101100101011110111100110010001100111000111101001110110111001000110011010111001110100101000010010000110001111001100001011101101101000011110101010100101110000100010011010001011000110000011100000100001010001000001101001000101100100101111100001010110010100100000000100110001100011011010001011001011001101000111000110111101111110100000011111001111000000100111000111010100110111011101000110101000001011011111011010110101011000000010101110101111111000101111010011000100101101001111101000011001001010110100010010000001110110001100100010100110110001100000001100110010001010001110101001101110111010001101010000010110111110110101101010110000000101011101011111110001011110100110001001011010011110110011111100100101011011001001100100000000110100111110010000110001101001101000010011010000001011001011011110001011110010010110011000100000000 Ni=10010001 verify=1
i=90 Si=1111100011 Mi=1100101101011111111101011001010100100011111111100110100001011010001011010001011100010000111111011110110111111001010011010111010110000100110000111110110001110100110011111000000001100011011000001011110101111001111010001101010001000011010010011101010100001001100111001110010111110111010100101110010001101011000111001110100111111101110111111010000000010101001110011011101000000100101000001000110011001001101101100110100010110111001000111111010010101100111000001101111000011001010101011010110110101011100111011001011111010111011000001011100100111100011001010100001100111111110110111001000001000101100011011101110111000100100100010011110010010111000010101001110011011101000000100101000001000110011001001101101100110100010110111001000111111010010101100111000001101111000011111000011110101001000000111001101001000100110110010100111011000001101111110100110100011100000000 Ni=111000100 verify=1
i=91 Si=1111101001 Mi=1100100101010111001101110110111100001100100000001111111101010011101110011011001101111111001101011000011010000001111010111010101110011010101000010011011111011000000010100110100110010111011001100000111011010100100000000110001001110111001011011101111110100101010101010101001110001100000011111010110110101000001110101000110111000110100000100000100010101101011110010011110110110001100111010000111110011001101100101000111010110110111101110100111110101000100010010001100001011001001001010010110001010110011110000111000100010001110111111010000010011101001110111000001100000110101101011000011100111010111011111000110011101000011111001100110110010100011101011011011110111010011111010100010001001000110000101100100100101001011000101011001111000011100001000001101110001110011100010011110001001000110010100111110010100101101000010001110111000001110110011110011000000100000000 Ni=11001010 verify=1
i=92 Si=1111111011 Mi=1100110010011010000010101010110000100101111011011101011111100111011000001010000000110010111101010110001011111111101111110010111010111000011001101011001001111010000100001011010111110011011010010110000111111010011100000000110000010111001111001000101010111100111100011101011100001000101110010001000001100001100011110010011111000000000000111111000110110011001110011000010011101100000011110001001011110011101010000001001000110010110110111101101010011001000011010101010010101000110100110100000100010011011100010100111000011010010100010110001110011110101100010110101011010000000100010101011000011100010101101011001111111000111101110010010010100100110001000111110110011001110011000010011101100000011110001001011110011101010000001001000110010110110111101101010011001000011010011001011100101110101100001011100000001100001111010010001110000110101010010011011011111100000000 Ni=10000001 verify=1
i=93 Si=10000001001 Mi=100010000110010111010001000010000000000100001110101100100111101101001000110100101100001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100010000110010111010001000010000000000100001110101100100111101101001000110100101100001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010001000011001011101000100001000000000010000111010110010011110110100100011010010110000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010001000011001011101000100001000000000010000111010110010011110110100100011010010110000100000000 Ni=110001010 verify=1
i=94 Si=10000001111 Mi=100010001010100010000100001100010001010011111110101011111011111111010000111111000001011000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100010001010100010000100001100010001010011111110101011111011111111010000111111000001011000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010001000101010001000010000110001000101001111111010101111101111111101000011111100000101100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010001000101010001000010000110001000101001111111010101111101111111101000011111100000101100000000 Ni=110010000 verify=1
i=95 Si=10000010001 Mi=100010110101100010110111001011110010010001010100101010110011010100111001001110111111001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100010110101100010110111001011110010010001010100101010110011010100111001001110111111001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010001011010110001011011100101111001001000101010010101011001101010011100100111011111100100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010001011010110001011011100101111001001000101010010101011001101010011100100111011111100100000000 Ni=1111101111 verify=1
i=96 Si=10000011011 Mi=100010100000110010101101010011000000111000101100100110101000011111010010011000011011111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100010100000110010101101010011000000111000101100100110101000011111010010011000011011111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010001010000011001010110101001100000011100010110010011010100001111101001001100001101111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010001010000011001010110101001100000011100010110010011010100001111101001001100001101111100000000 Ni=110001111 verify=1
i=97 Si=10000011101 Mi=100010101100000111110110011000001110100110101010110100100011100100000001110101000000101000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100010101100000111110110011000001110100110101010110100100011100100000001110101000000101000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010001010110000011111011001100000111010011010101011010010001110010000000111010100000010100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010001010110000011111011001100000111010011010101011010010001110010000000111010100000010100000000 Ni=1111010100 verify=1
i=98 Si=10000100111 Mi=100011011101000111000000100010101110100101100000011001111100000011110111100111000000011000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100011011101000111000000100010101110100101100000011001111100000011110111100111000000011000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010001101110100011100000010001010111010010110000001100111110000001111011110011100000001100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010001101110100011100000010001010111010010110000001100111110000001111011110011100000001100000000 Ni=111110010 verify=1
i=99 Si=10000101101 Mi=100011001000010110000000001111111110001111001110001111001001110101001010010011110110101000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100011001000010110000000001111111110001111001110001111001001110101001010010011110110101000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010001100100001011000000000111111111000111100111000111100100111010100101001001111011010100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010001100100001011000000000111111111000111100111000111100100111010100101001001111011010100000000 Ni=101011101 verify=1
r~=111000100000000001010110011111101100011100110000110001001000010001011000010000100100100111100101110000010000010000001110100010011100111101111110001011100001001111110110010011010110000011000101100010010011010000111111111110001010100010110111111100000001111110001001101001111111101000000101111011111100110011101011000010001111010001111111111011100111001111101111101011011101000010110101110011011001001001100111100100000101000010001110010001110100110110011011001001101101101101110000000011001001010001000010111000011110110001111110001001001010110110111001011010000110101001000110100100010110100011010100101000010100010111111100111100000000111010110001001000101001001001110000000111110011010111011110101001100000100000001011010001100011110110101110110110110001001010000101001100110101111010010001111101111001111010010000100101000110000011010110010010010111111000000100101000110110 r=10111011011011100100110110011111011010001110011001110110010001011101100100111100000101100110011010000010000001110100010011100111101111110001011100001001111110110010011010110000011000101100010010011010000111111111110001010100010110111111100000001111001001111010010101110111111001110000111000000111011111011110110010101001110011111100011011110000111110111101011011101000010110101110011011001001001100111100100000101000010001110010001110100110110011011001001101101101101110000000011001001010001000010111000000010101010010011001100010110011001001010101010100111101010010111001101101000100010110111001100110101110111111100111100000000111010110001001000101001001001110000000111110011010111011110101001100000100000001011010001100011110110101110110110110001001010000110101111101000010010111010011000000111100100010100101101011100001110011001100010011011100100100000100100110110
i=0 Oi=110110 O~i=110110 cmp=0
i=1 Oi=111010 O~i=111010 cmp=0
i=2 Oi=101100 O~i=101100 cmp=0
i=3 Oi=111110 O~i=111110 cmp=0
i=4 Oi=1100 O~i=1100 cmp=0
i=5 Oi=11010 O~i=11010 cmp=0
i=6 Oi=1011101 O~i=1011101 cmp=0
i=7 Oi=1000011 O~i=1000011 cmp=0
i=8 Oi=1100001 O~i=1100001 cmp=0
i=9 Oi=111000 O~i=111000 cmp=0
i=10 Oi=110110 O~i=110110 cmp=0
i=11 Oi=101011 O~i=101011 cmp=0
i=12 Oi=11111 O~i=11111 cmp=0
i=13 Oi=101011 O~i=101011 cmp=0
i=14 Oi=1010000 O~i=1010000 cmp=0
i=15 Oi=111100 O~i=111100 cmp=0
i=16 Oi=100 O~i=100 cmp=0
i=17 Oi=1000000 O~i=1000000 cmp=0
i=18 Oi=1011010 O~i=1011010 cmp=0
i=19 Oi=100000 O~i=100000 cmp=0
i=20 Oi=11101 O~i=11101 cmp=0
i=21 Oi=111 O~i=111 cmp=0
i=22 Oi=1010 O~i=1010 cmp=0
i=23 Oi=1001000 O~i=1001000 cmp=0
i=24 Oi=100110 O~i=100110 cmp=0
i=25 Oi=100110 O~i=100110 cmp=0
i=26 Oi=1000 O~i=1000 cmp=0
i=27 Oi=101110 O~i=101110 cmp=0
i=28 Oi=1000101 O~i=1000101 cmp=0
i=29 Oi=11011 O~i=11011 cmp=0
i=30 Oi=111101 O~i=111101 cmp=0
i=31 Oi=1010110 O~i=1010110 cmp=0
i=32 Oi=110000 O~i=110000 cmp=0
i=33 Oi=100010 O~i=100010 cmp=0
i=34 Oi=101100 O~i=101100 cmp=0
i=35 Oi=111001 O~i=111001 cmp=0
i=36 Oi=1100000 O~i=1100000 cmp=0
i=37 Oi=1010101 O~i=1010101 cmp=0
i=38 Oi=1100001 O~i=1100001 cmp=0
i=39 Oi=11011 O~i=11011 cmp=0
i=40 Oi=11 O~i=11 cmp=0
i=41 Oi=11101 O~i=11101 cmp=0
i=42 Oi=111 O~i=111 cmp=0
i=43 Oi=10111 O~i=10111 cmp=0
i=44 Oi=1000110 O~i=1000110 cmp=0
i=45 Oi=1011 O~i=1011 cmp=0
i=46 Oi=1011100 O~i=1011100 cmp=0
i=47 Oi=101001 O~i=101001 cmp=0
i=48 Oi=11101 O~i=11101 cmp=0
i=49 Oi=100111 O~i=100111 cmp=0
i=50 Oi=11000 O~i=11000 cmp=0
i=51 Oi=111001 O~i=111001 cmp=0
i=52 Oi=1010001 O~i=1010001 cmp=0
i=53 Oi=100100 O~i=100100 cmp=0
i=54 Oi=11110 O~i=11110 cmp=0
i=55 Oi=10111 O~i=10111 cmp=0
i=56 Oi=11011 O~i=11011 cmp=0
i=57 Oi=1000000 O~i=1000000 cmp=0
i=58 Oi=1010111 O~i=1010111 cmp=0
i=59 Oi=1011011 O~i=1011011 cmp=0
i=60 Oi=11 O~i=11 cmp=0
i=61 Oi=111000 O~i=111000 cmp=0
i=62 Oi=1001001 O~i=1001001 cmp=0
i=63 Oi=1000001 O~i=1000001 cmp=0
i=64 Oi=10100 O~i=10100 cmp=0
i=65 Oi=1100001 O~i=1100001 cmp=0
i=66 Oi=1011001 O~i=1011001 cmp=0
i=67 Oi=1011101 O~i=1011101 cmp=0
i=68 Oi=1000111 O~i=1000111 cmp=0
i=69 Oi=110010 O~i=110010 cmp=0
i=70 Oi=1011110 O~i=1011110 cmp=0
i=71 Oi=101010 O~i=101010 cmp=0
i=72 Oi=110111 O~i=110111 cmp=0
i=73 Oi=1010010 O~i=1010010 cmp=0
i=74 Oi=100001 O~i=100001 cmp=0
i=75 Oi=110 O~i=110 cmp=0
i=76 Oi=101000 O~i=101000 cmp=0
i=77 Oi=1011101 O~i=1011101 cmp=0
i=78 Oi=101110 O~i=101110 cmp=0
i=79 Oi=10100 O~i=10100 cmp=0
i=80 Oi=1 O~i=1 cmp=0
i=81 Oi=1001111 O~i=1001111 cmp=0
i=82 Oi=10101 O~i=10101 cmp=0
i=83 Oi=10001 O~i=10001 cmp=0
i=84 Oi=11000 O~i=11000 cmp=0
i=85 Oi=11001 O~i=11001 cmp=0
i=86 Oi=1010010 O~i=1010010 cmp=0
i=87 Oi=11011 O~i=11011 cmp=0
i=88 Oi=1000100 O~i=1000100 cmp=0
i=89 Oi=1000 O~i=1000 cmp=0
i=90 Oi=110110 O~i=110110 cmp=0
i=91 Oi=100100 O~i=100100 cmp=0
i=92 Oi=1011010 O~i=1011010 cmp=0
i=93 Oi=1011000 O~i=1011000 cmp=0
i=94 Oi=1000010 O~i=1000010 cmp=0
i=95 Oi=11011 O~i=11011 cmp=0
i=96 Oi=101 O~i=101 cmp=0
i=97 Oi=11111 O~i=11111 cmp=0
i=98 Oi=1001111 O~i=1001111 cmp=0
i=99 Oi=10010 O~i=10010 cmp=0

On 10/26/21 15:57, mc36 wrote:

hi,
i go inline....
regards,
cs

On 10/26/21 15:26, Cristina Klippel Dominicini wrote:

Hi Csaba,

Sorry for the delay. We are finishing some hard deadlines from our side until
the end of this week.

no problem, take your time!

Thank you very much for filling the gaps between our academic idea and a
proposal that can be deployed in production. This discussion interests us a
lot!

Your suggestions for TTL and the abuse of the output port seem great. However, I still need some time to ponder how it impacts on two (maybe naive) premises of our paper: A fully stateless protocol that does not depend on tables at all, and does not execute packet rewrites*.
the peernodeid-->nexthop table can be considered static or at least rarely
changing...
the ttl decrease is really a rewrite, but it's almost mandatory thing in
networking... :)
also, the underlaying ethernet header rewrite is also mandatory, otherwise,
polka packets
cannot travelse bridged networks, such as vpls or learning media converters...

In the paper, as a proof-of-concept, we considered a programmable fabric network and did not consider the interoperability issues using a clean state approach. In the real world, when we apply your suggestions, the original benefits of our proposal are reduced when compared to related works, such as segment routing.
segment routing does traffic engineering by applying multiple labels which is
simply ugly,
and most real commercial gear have low hard limit on the number of labels
that can handle,
so nowadays they advertise maximum label depth router capabilities in routing
protocols...
so polka still have the benefit here as one can express longer paths than
these limits...

Maybe, there is an intermediary solution. This discussion is very valuable.
I'll get back to you soon with more elaborated feedback.

so these were just my first raw ideas, we should think about these things
further....

Best regards,
Cristina

* Our original implementation in bmv2 actually uses lookahead and does not
parse the header, but we haven't ported this to Tofino yet.

________________________________________
De: mc36 <>
Enviado: sÃ¡bado, 23 de outubro de 2021 01:53
Para: Cristina Klippel Dominicini
Cc: Rafael Silva GuimarÃ£es;
Assunto: polka is approaching rare... was: Re: custom crc32 library in
freerouter

hi,

i was thinking a lot about how to proceed when i'll get the math code from
you, and i came up with the following two:

introduce ttl in polka:
as discussed during the vc, a fail-proof protocol should have a last resport
safeguard against routing loops...
at the polka patch i have, you allocated a 16 bit version field, so my idea
is to split that one into two
8bit parts, one for verison and the other for ttl, which must be decremented
on every forwarding node,
and the packet must be discarded when it reaches zero...

abuse output port:
at the paper, you describe the polka forwarding calculation results directly
in the output port...
in the polka patch you conclude to polka_portid, which is good for proof of
concept testing,
but it will not work in the wild... first of all, just concluding to a portid
cannot result in
layer2 header rewrites: that is, on a given link, the ethernet.srcaddr must
be the sender, and
the ethernet.dstaddr must be the remote, who you will to forward to... on
point to point
connections, basically yuo can abuse ethernet and send with arbitrary
ethernet addresses,
but on switched lans, it won't work at all... so the portid alone is not
enough, moreover,
the current routing protocols does notfloods this information nor in the igp
or bgp databases...
so to have the ethernet rewrite info at hand, and to support broadcast lans,
where you could
have two neighbors on a given link, at least a nexthopid should be encoded,
but it's the same
story, no any current protocol encodes this info into the databases...
okk, we could ask ietf for new code points to store this info in the long
run, but it's time...
so for now, my idea here is to abuse polka's portid and encode the target
nodeid instead...
it'll result in an additional table lookup in the ig_ctl_polka.p4 but it'll
solve all the above...
for preparation to this, i introduced a new outcome from some routing
protocols in freerouter,
the index to prefix mapping table... here is the commit, and below the output
from my homenet...
https://github.com/mc36/freeRouter/commit/b27377c6da5c6f7c7eab7766dbc509a8e6310853
so from now, lsrp, ospf, isis and bgp all populate this table correctly, so
these will
have polka support... this table will be sent to the dataplane, and the
polka.portid
will be looked up in this table to have a nexthopid to forward the packet
to...
you will not have to do anything about this in your part of the code, i'll
silently
use your routeid encoder this way....

i'm seeking your insight on the above...

regards,
cs

noti#show ipv6 srindex inet
indexÂ prefix
10Â Â Â Â 2001:db8:1101::1/128
20Â Â Â Â 2001:db8:1101::2/128
24Â Â Â Â 2001:db8:1101::10/128
25Â Â Â Â 2001:db8:1101::1101/128
26Â Â Â Â 2001:db8:1101::11:11/128
27Â Â Â Â 2001:db8:1101::26/128
29Â Â Â Â 2001:db8:1101::29/128
31Â Â Â Â 2001:db8:1101::31/128
32Â Â Â Â 2001:db8:1101::24/128
33Â Â Â Â 2001:db8:1101::25/128
40Â Â Â Â 2001:db8:1101::4/128
50Â Â Â Â 2001:db8:1101::5/128
54Â Â Â Â 2001:db8:36::1/128
80Â Â Â Â 2001:db8:1101::8/128
97Â Â Â Â 2001:db8:1101::222:222/128
110Â Â Â ::/0
180Â Â Â 2001:db8:1101::18/128
181Â Â Â 2001:db8:1101::180/128
190Â Â Â 2001:db8:1101::19/128
191Â Â Â 2001:db8:1101::190/128
193Â Â Â 2001:db8:1101::252:198/128
197Â Â Â 2001:db8:1101::252:197/128
199Â Â Â 2001:db8:1101::199/128
200Â Â Â 2001:db8:1101::20/128
210Â Â Â 2001:db8:1101::21/128
240Â Â Â 2001:db8:1101::240/128
260Â Â Â 2001:db8:1101::27/128
270Â Â Â 2001:db8:1026:1001::2/128

noti#

On 10/22/21 16:58, mc36 wrote:

hi,
excellent news, thanks!
i'm waiting for your code, then i'll start integrating asap!
have a nice weekend,
regards,
cs

On 10/22/21 16:41, Cristina Klippel Dominicini wrote:

Hi Csaba,

Just to let you know. The Java ring lib worked like a charm :-) I just need
to double check some Math considerations, because the representation of the
libs are a bit different.
I have already translated our code to Java, and on Monday I will execute the
final tests and send to you a stable version.

Best regards,
Cristina

________________________________________
De: mc36 <>
Enviado: quinta-feira, 21 de outubro de 2021 02:13
Para: Cristina Klippel Dominicini; Cristina Klippel Dominicini; Rafael S.
Guimaraes; Rafael S. GuimarÃÂ£es
Cc: ; Magnos Martinello; Moises R. N. Ribeiro
Assunto: Re: custom crc32 library in freerouter

hi,

lib: okk, pick any lib you see fit and convenient for you...

github: it's me: https://github.com/mc36/

finally, i'am also very excited that we're getting closer and closer to
polka....
when i first read your paper, i had the feeling that it's an excellent idea!
:)

thanks,
cs

On 10/21/21 03:40, Cristina Klippel Dominicini wrote:

Hi, Csaba,

These are great news! I am very happy to learn that Tofino now supports the
polynomial configuration in runtime by the control plane. Thanks for asking
the question to Vladimir
in the FASTER forum.

Indeed, we use only basic arithmetic functions from sympy, and calculate the
multiplicative inverse. Could you please send your github user to us? Then,
we can share our
repository of our python lib.

I will double check tomorrow, but the following lib in Java seems to have all
the required methods: https://rings.readthedocs.io/en/latest/
It is Apache License: https://github.com/PoslavskySV/rings

Thank you very much for your support. We are looking forward to integrate
PolKA in FreeRouter :-)

Best regards,
Cristina

________________________________________
De: mc36 <>
Enviado: quarta-feira, 20 de outubro de 2021 00:26
Para: Cristina Klippel Dominicini; Cristina Klippel Dominicini; Rafael S.
Guimaraes; Rafael S. GuimarÃfÃÂ£es
Cc:
Assunto: Re: custom crc32 library in freerouter

hi.
sorry for the spam but i forgot to tell you a great news:
as some of us was already involved in this thread, i asked vlad if they
progressed with the crc,
and it seems that yess, they did, we can set the coeff from the control
plane, hurray:
https://community.intel.com/t5/Intel-Connectivity-Research/Changing-CRC-polynomial-from-the-control-plane/m-p/1323312
regards,
cs

On 10/20/21 05:15, mc36 wrote:

hi,

thanks for the quick response... i reply topic by topic...

crc:
just a small footnote that i refactored them again to get back the original
speeds...
the trick there was that it was a static final table that is, it was common
for all the
classes, so it was computed only once... now it's true again...:)
not that much happened, just the class instantination parameter changed...

sympy:
after a quick look, it seems to me a huuuge (33mb) symbolic math package...
but in guess you're only using a small subset of that... at least from the
paper,
my bet is that you only need a class that represents a polynomial, and the
add, sub, div, mul functions over it (as i shown for ellitic curves during
the vc)
so if that's the case, i would suggest you that simply give me some time and
let me come up with something that can calculate only these over a poly
class...
if you could shar your current python code could help me to see what you need
from sympy...
i really love doing such things because it refreshes a bit the things i learnt
during the university classes, and i really like explore and understand
things...
finally, calling out to external libs are always costy because of the
java-ish overhead that is put by the non-specific libs, and when you
have an unstable network and you have to recompute frequently then it
pays off to have everything in hand that you can fully optimize...
snoopy.vhpc#show platform | include uptime
uptime: since 2021-10-16 10:00:37, for 3d18h
snoopy.vhpc#show ipv4 bgp 1955 bestpath | include change
changes allÃf' Ãf' Ãf' Ãf' Ãf'ÃÂ 15784774
changes nowÃf' Ãf' Ãf' Ãf' Ãf'ÃÂ 37
snoopy.vhpc#
it's the worst example i have for the above, it averages to 45 changes /
second...

reusing segment routing id from routing protocols:
so at the moment it's the quickest way i see to fit the need to populate an
id->prefix
and prefix->id table on each node in a network... also keep in mind that
freerouter have
homebrew routing protocols too (http://lsrp.nop.hu/ and
http://pvrp.nop.hu/)... so if we
need a new value somehow, it can arrive in no time to continue
experimenting...
but in a longer run, you should consider ietf rfcs to have specific values
just for polka...

thanks,
cs

On 10/20/21 03:00, Cristina Klippel Dominicini wrote:

Hi, Csaba,

Thank you very much for this quick response!

Yes! The bmv2 implementation explores predefined tables (code below) for
well-known CRC standards and builds the tables for custom polynomials.
https://github.com/p4lang/behavioral-model/blob/main/src/bm_sim/crc_tables.h
Their solution was inspired by this code that offers a nice introduction to
the CRC calculation:
https://barrgroup.com/Embedded-Systems/How-To/CRC-Calculation-C-Code

Your new code seems to fit our requirements perfectly. We will execute some
tests with default parameters to double check.

We used CRC16, because the lower the polynomial degree, the better in terms
of the bitlength of the routeid. In theory, we could use lower polynomials
for small topologies, but
we got some errors with CRC8 in our initial tests in Tofino. We will check if
we can use CRC8 in Tofino.

Now, we are going to translate our code to provide you with a Java method that performs the routeID computation given the path information (set of the nodeIDs and portIDs). Most
of our polynomial computation uses the galoisfield module of the sympy lib
(https://docs.sympy.org/latest/modules/polys/index.html). So, I will check if
there is a similar
library in Java. For the nodeid computation, it is just a matter of
calculating a list of irreducible polynomials, so it should suffice to have a
fixed list of nodeids for the
control plane.

Finally, your suggestion to use BGP/IGP for node discovery and reuse the
Segment Routing identifiers seems to be a very elegant solution. We will
study that. Thank you!

Best regards,
Cristina

________________________________________
De: mc36 <>
Enviado: terÃffÃ'ÃÂ§a-feira, 19 de outubro de 2021 17:21
Para: Cristina Klippel Dominicini; Cristina Klippel Dominicini; Rafael S.
Guimaraes; Rafael S. GuimarÃffÃ'ÃÂ£es
Cc:
Assunto: Re: custom crc32 library in freerouter

hi,
sorry for the spam again, but i checked again the polka.patch and found that
maybe you're using crc16?
so here we go, i also parameterized it in freertr:
http://src.mchome.nop.hu/src/net/freertr/cry/cryHashCrc16.java
with this:
https://github.com/mc36/freeRouter/commit/4958add8b8fc48f1a35199f6e57deeb5dfe768ac
i'm never against some good refactoring, afterall... :)
also, you really should check the last but one vc, we demoed how
segment-routing traffic engineering can work...
that is my intent to reach to that same level with polka, with abusing the
already existing igp's and/or bgp's
segrout.index flooding mechanisms... here is the video:
https://www.youtube.com/watch?v=jS6RmHKC4aQ
regards,
cs

On 10/19/21 21:31, mc36 wrote:

hi,
sorry for the spam...
so i played a bit with my crc32 library and found out that i can calculate
the same values with a single class,
just some parameters need to be passed to it become the "ieee ethernet" or the
"sctp rfc" version of the crc code...
here is what freertr have now at the moment:
http://sources.nop.hu/src/net/freertr/cry/cryHashCrc32.java
(my bad, the url was bad in the previous mail...:) and this is what happened
in the code to reach the single class:
https://github.com/mc36/freeRouter/commit/ca58d4fe39f0cd681d6cd21d3a9a2474e07600a8
if you still need a parameter or anything around the crypto lib, just let me
know...
but hopefully now, it'll be easy for you to come up with the rest, that is:
Ãf'ÃÂ Ãff' - a method to encode the polka.routeid from "List<Integer>
nodes"...
Ãf'ÃÂ Ãff' - a method to calculate the coefficient (polynominal?) from a
single node id...
then we can finally have a pure java forwarder and so on, as we discussed in
the vc...
thanks,
cs

On 10/19/21 17:34, mc36 wrote:

hi

i've found the crc32_custom magic in bmv2:

behavioral-model-main/src/bm_sim/crc_map.cpp
behavioral-model-main/src/bm_sim/calculations.cpp

in the crc_map.cpp for crc32c, they uses the same magic as me at
http://source.nop.hu/src/net/freertr/cry/cryHashCrc32c.java
and the table calculation in calculations.cpp seems similar that i do too,
but mine works with fixed magic...

but they have no parameter called coefficiet, but the magic called
polynomial...

my best guess according to
https://en.wikipedia.org/wiki/Cyclic_redundancy_check is that they're the
same?
(but again, it's my bad but i'm a bit noob in these math things, i'm much
more a networker and coder guy:)

so if that's the case then i'll create a new crc32 class that needs to be
initialized with the poly paramareter...

thanks,

cs

________________________________

Esta mensagem (incluindo anexos) contÃffÃ'ÃÂ©m informaÃffÃ'ÃÂ§ÃffÃ'ÃÂ£o confidencial destinada a um usuÃffÃ'ÃÂ¡rio especÃffÃ'ÃÂfico e seu conteÃffÃ'ÃÂºdo ÃffÃ'ÃÂ© protegido por lei. Se vocÃffÃ'ÃÂª nÃffÃ'ÃÂ£o
ÃffÃ'ÃÂ© o destinatÃffÃ'ÃÂ¡rio correto deve
apagar esta mensagem.

O emitente desta mensagem ÃffÃ'ÃÂ© responsÃffÃ'ÃÂ¡vel por seu
conteÃffÃ'ÃÂºdo e endereÃffÃ'ÃÂ§amento.
Cabe ao destinatÃffÃ'ÃÂ¡rio cuidar quanto ao tratamento adequado. A divulgaÃffÃ'ÃÂ§ÃffÃ'ÃÂ£o, reproduÃffÃ'ÃÂ§ÃffÃ'ÃÂ£o e/ou distribuiÃffÃ'ÃÂ§ÃffÃ'ÃÂ£o sem a devida autorizaÃffÃ'ÃÂ§ÃffÃ'ÃÂ£o ou qualquer outra
aÃffÃ'ÃÂ§ÃffÃ'ÃÂ£o sem conformidade com as
normas internas do Ifes sÃffÃ'ÃÂ£o proibidas e passÃffÃ'ÃÂveis de
sanÃffÃ'ÃÂ§ÃffÃ'ÃÂ£o disciplinar, cÃffÃ'ÃÂvel e criminal.

________________________________

Esta mensagem (incluindo anexos) contÃfÃÂ©m informaÃfÃÂ§ÃfÃÂ£o confidencial destinada a um usuÃfÃÂ¡rio especÃfÃÂfico e seu conteÃfÃÂºdo ÃfÃÂ© protegido por lei. Se vocÃfÃÂª nÃfÃÂ£o ÃfÃÂ© o destinatÃfÃÂ¡rio
correto deve apagar esta mensagem.

O emitente desta mensagem ÃfÃÂ© responsÃfÃÂ¡vel por seu conteÃfÃÂºdo e
endereÃfÃÂ§amento.
Cabe ao destinatÃfÃÂ¡rio cuidar quanto ao tratamento adequado. A divulgaÃfÃÂ§ÃfÃÂ£o, reproduÃfÃÂ§ÃfÃÂ£o e/ou distribuiÃfÃÂ§ÃfÃÂ£o sem a devida autorizaÃfÃÂ§ÃfÃÂ£o ou qualquer outra aÃfÃÂ§ÃfÃÂ£o sem conformidade
com as normas internas do Ifes sÃfÃÂ£o proibidas e passÃfÃÂveis de
sanÃfÃÂ§ÃfÃÂ£o disciplinar, cÃfÃÂvel e criminal.

________________________________

Esta mensagem (incluindo anexos) contÃÂ©m informaÃÂ§ÃÂ£o confidencial destinada a um usuÃÂ¡rio especÃÂfico e seu conteÃÂºdo ÃÂ© protegido por lei. Se vocÃÂª nÃÂ£o ÃÂ© o destinatÃÂ¡rio correto deve
apagar esta mensagem.

O emitente desta mensagem ÃÂ© responsÃÂ¡vel por seu conteÃÂºdo e
endereÃÂ§amento.
Cabe ao destinatÃÂ¡rio cuidar quanto ao tratamento adequado. A divulgaÃÂ§ÃÂ£o, reproduÃÂ§ÃÂ£o e/ou distribuiÃÂ§ÃÂ£o sem a devida autorizaÃÂ§ÃÂ£o ou qualquer outra aÃÂ§ÃÂ£o sem conformidade com as
normas internas do Ifes sÃÂ£o proibidas e passÃÂveis de sanÃÂ§ÃÂ£o
disciplinar, cÃÂvel e criminal.

________________________________

Esta mensagem (incluindo anexos) contÃ©m informaÃ§Ã£o confidencial destinada a um usuÃ¡rio especÃfico e seu conteÃºdo Ã© protegido por lei. Se vocÃª nÃ£o Ã© o destinatÃ¡rio correto deve apagar esta mensagem.

O emitente desta mensagem Ã© responsÃ¡vel por seu conteÃºdo e endereÃ§amento.
Cabe ao destinatÃ¡rio cuidar quanto ao tratamento adequado. A divulgaÃ§Ã£o, reproduÃ§Ã£o e/ou distribuiÃ§Ã£o sem a devida autorizaÃ§Ã£o ou qualquer outra aÃ§Ã£o sem conformidade com as normas internas do Ifes sÃ£o proibidas e passÃveis de sanÃ§Ã£o disciplinar, cÃvel e criminal.

import java.math.BigInteger;
import java.util.Random;

public class poly implements Comparable<poly> {

    private static void testMI(poly a, poly n) {
        poly[] r = a.modInv(n);
        System.out.println("a=" + a + " n=" + n + " inv=" + r[0] + " gcd=" + r[1]);
        if (r[0] == null) {
            return;
        }
        System.out.println("verify=" + r[0].mul(a).div(n)[1]);
    }
    
    private static void testSI(poly[] s, poly[] o) {
        System.out.println("****************************************************");
        poly M = s[0];
        for (int i = 1; i < s.length; i++) {
            M = M.mul(s[i]);
        }
        poly[] m = new poly[s.length];
        poly[] n = new poly[s.length];
        for (int i = 0; i < s.length; i++) {
            m[i] = M.div(s[i])[0];
            n[i] = m[i].modInv(s[i])[0];
        }
        System.out.println("M=" + M);
        for (int i = 0; i < s.length; i++) {
            System.out.println("i=" + i + " Si=" + s[i] + " Mi=" + m[i] + " Ni=" + n[i] + " verify=" + n[i].mul(m[i]).div(s[i])[1]);
        }
        poly r = new poly(BigInteger.valueOf(0));
        for (int i = 0; i < s.length; i++) {
            r = r.add(o[i].mul(m[i]).mul(n[i]));
        }
        System.out.println("r~=" + r + " r=" + r.div(M)[1]);
        r = r.div(M)[1];
        for (int i = 0; i < s.length; i++) {
            poly c = r.div(s[i])[1];
            System.out.println("i=" + i + " Oi=" + o[i] + " O~i=" + c + " cmp=" + o[i].compareTo(c));
        }
    }
    
    private static void testSI(poly[] s) {
        Random rnd = new Random();
        poly[] o = new poly[s.length];
        for (int i = 0; i < s.length; i++) {
            o[i] = new poly(BigInteger.valueOf(rnd.nextInt(s.length)));
        }
        testSI(s, o);
    }
    
    private static boolean genS(poly[] s, int o, int f) {
        for (int i = 0; i < o; i++) {
            poly[] r = s[i].modInv(new poly(f));
            if (r == null) {
                return true;
            }
            if (r[0] == null) {
                return true;
            }
        }
        return false;
    }
    
    private static poly[] genS(int f, int n) {
        poly[] s = new poly[n];
        s[0] = new poly(f);
        for (int o = 1; o < s.length; o++) {
            for (;;) {
                f++;
                if (genS(s, o, f)) {
                    continue;
                }
                break;
            }
            s[o] = new poly(f);
        }
        return s;
    }
    
    public static void main(String[] args) {
        System.out.println(new poly("111").add(new poly("11")) + " = 100");
        System.out.println(new poly("111").mul(new poly("101")) + " = 11011");
        System.out.println(new poly("1000000001").add(new poly("1001001")) + " = 1001001000");
        System.out.println(new poly("1000000001").mul(new poly("1001001")) + " = 1001001001001001");
        System.out.println(new poly("11011").mul(new poly("101")) + " = 1110111");
        System.out.println(new poly("10111000111010000000011").div(new poly("111"))[0] + " = 111110111110000000000");
        testMI(new poly("111011"), new poly("1111111111110000000"));
//        0x2b,0x2d,0x39,0x3f,0x47,0x53,0x8d,0xbd,0xd7,0xf5
        testMI(new poly(0x3f), new poly(0x53));
        testMI(new poly(0x53), new poly(0x3f));
        testSI(new poly[]{new poly("11"), new poly("111"), new poly("1011")},
                new poly[]{new poly("1"), new poly("10"), new poly("110")});
        testSI(genS(256, 100));
    }
    
    private final BigInteger coeff;

    /**
     * create instance
     *
     * @param c coefficient
     */
    public poly(BigInteger c) {
        coeff = c;
    }

    /**
     * create instance
     *
     * @param c coefficient
     */
    public poly(int c) {
        coeff = BigInteger.valueOf(c);
    }

    /**
     * create instance
     *
     * @param c coefficient
     */
    public poly(String c) {
        coeff = new BigInteger(c, 2);
    }
    
    public String toString() {
        return coeff.toString(2);
    }
    
    public int compareTo(poly o) {
        return coeff.compareTo(o.coeff);
    }
    
    private static BigInteger mul(BigInteger c, BigInteger a) {
        BigInteger r = BigInteger.valueOf(0);
        int s = c.bitLength();
        for (int i = 0; i < s; i++) {
            if (c.testBit(0)) {
                r = r.xor(a);
            }
            c = c.shiftRight(1);
            a = a.shiftLeft(1);
        }
        return r;
    }
    
    private static BigInteger[] div(BigInteger r, BigInteger d) {
        int s = d.bitLength();
        if (s < 1) {
            return null;
        }
        s = r.bitLength() - s;
        if (s < 1) {
            s = 0;
        }
        BigInteger p = BigInteger.valueOf(1).shiftLeft(s);
        BigInteger q = BigInteger.valueOf(0);
        d = d.shiftLeft(s);
        for (int i = 0; i <= s; i++) {
            if (r.bitLength() == d.bitLength()) {
                r = r.xor(d);
                q = q.xor(p);
            }
            d = d.shiftRight(1);
            p = p.shiftRight(1);
        }
        return new BigInteger[]{q, r};
    }
    
    private static BigInteger[] modInv(BigInteger nr, BigInteger r) {
        // extended euclidean algorithm
        BigInteger t = BigInteger.valueOf(0);
        BigInteger nt = BigInteger.valueOf(1);
        for (;;) {
            if (nr.bitLength() < 1) {
                break;
            }
            BigInteger[] q = div(r, nr);
            if (q == null) {
                return null;
            }
            BigInteger ot = nt;
            BigInteger or = nr;
            nt = t.xor(mul(q[0], nt));
            nr = r.xor(mul(q[0], nr));
            t = ot;
            r = or;
        }
        if (r.bitLength() > 1) {
            t = null;
        }
        return new BigInteger[]{t, r};
    }

    /**
     * addition
     *
     * @param o other
     * @return result
     */
    public poly add(poly o) {
        return new poly(coeff.xor(o.coeff));
    }

    /**
     * subtract
     *
     * @param o other
     * @return result
     */
    public poly sub(poly o) {
        return new poly(coeff.xor(o.coeff));
    }

    /**
     * multiplication
     *
     * @param o other
     * @return result
     */
    public poly mul(poly o) {
        return new poly(mul(o.coeff, coeff));
    }

    /**
     * division
     *
     * @param o other
     * @return array of result,remainder
     */
    public poly[] div(poly o) {
        BigInteger[] r = div(coeff, o.coeff);
        if (r == null) {
            return null;
        }
        return new poly[]{new poly(r[0]), new poly(r[1])};
    }

    /**
     * multiplicative inverse
     *
     * @param o other
     * @return array of result,gcd
     */
    public poly[] modInv(poly o) {
        BigInteger[] r = modInv(coeff, o.coeff);
        if (r == null) {
            return null;
        }
        if (r[0] == null) {
            return new poly[]{null, new poly(r[1])};
        }
        return new poly[]{new poly(r[0]), new poly(r[1])};
    }
    
}

[rare-dev] custom crc32 library in freerouter, mc36, 10/19/2021
- Re: [rare-dev] custom crc32 library in freerouter, mc36, 10/19/2021
  - Re: [rare-dev] custom crc32 library in freerouter, mc36, 10/19/2021
    - Message not available
      - Re: [rare-dev] custom crc32 library in freerouter, mc36, 10/20/2021
        
        Re: [rare-dev] custom crc32 library in freerouter, mc36, 10/20/2021
        
        Message not available
        
        Re: [rare-dev] custom crc32 library in freerouter, mc36, 10/21/2021
        Message not available
        Re: [rare-dev] custom crc32 library in freerouter, mc36, 10/22/2021
        [rare-dev] polka is approaching rare... was: Re: custom crc32 library in freerouter, mc36, 10/23/2021
        Message not available
        Re: [rare-dev] polka is approaching rare... was: Re: custom crc32 library in freerouter, mc36, 10/26/2021
        Re: [rare-dev] polka is approaching rare... was: Re: custom crc32 library in freerouter, mc36, 10/27/2021
        Re: [rare-dev] polka is approaching rare... was: Re: custom crc32 library in freerouter, mc36, 10/27/2021
        Re: [rare-dev] polka is approaching rare... was: Re: custom crc32 library in freerouter, mc36, 10/27/2021
        Re: [rare-dev] polka is approaching rare... was: Re: custom crc32 library in freerouter, mc36, 10/27/2021
        Re: [rare-dev] polka is approaching rare... was: Re: custom crc32 library in freerouter, mc36, 10/27/2021
        Message not available
        Re: [rare-dev] polka is approaching rare... was: Re: custom crc32 library in freerouter, mc36, 10/28/2021
        Re: [rare-dev] polka is approaching rare... was: Re: custom crc32 library in freerouter, mc36, 10/28/2021
        Re: [rare-dev] polka is approaching rare... was: Re: custom crc32 library in freerouter, mc36, 10/30/2021
        Re: [rare-dev] polka is approaching rare... was: Re: custom crc32 library in freerouter, Frédéric LOUI, 10/30/2021
        Re: [rare-dev] polka is approaching rare... was: Re: custom crc32 library in freerouter, mc36, 10/30/2021

List archive

Re: [rare-dev] polka is approaching rare... was: Re: custom crc32 library in freerouter