Thursday 2 May 2019

number theory - Residue distributions are not uniform

With $n_1$ and $n_2$ two positive integers, the formula



$$L = \sum_{k=0}^{498}\, \left(n_1+n_2\, k \right) {(10^{6})}^{k}$$



can construct very large numbers $L$.



Once we have $L$ we can let $n$ vary from $1$ to $1,000,000$ and construct residues




$$n \mapsto [L \pmod n] \pmod {53}$$



The residues will all belong to $\{0,1,2,\dots,52\}$. Since we are taking $1,000,000$ residues, you might guess that each residue will occur around $\frac{10^6}{53} \approx 18,868$ times, but this is not the case.



I wrote a Python program (see next section) and found the following distributions:



Please input big number seed 1: 1
Please input big number seed 2: 2
seeds = 1 2
[(16, 37359), (25, 19262), (4, 19164), (13, 19153), (26, 18985), (1, 18972), (41, 18885), (15, 18855), (12, 18814), (7, 18766), (46, 18766), (29, 18755), (50, 18746), (20, 18735), (10, 18716), (39, 18701), (9, 18638), (33, 18638), (45, 18626), (48, 18575), (18, 18573), (43, 18569), (31, 18527), (22, 18511), (5, 18509), (2, 18459), (8, 18454), (38, 18449), (21, 18443), (0, 18440), (34, 18430), (49, 18422), (23, 18416), (47, 18413), (35, 18409), (17, 18405), (42, 18401), (27, 18400), (36, 18399), (28, 18321), (32, 18320), (14, 18302), (3, 18294), (24, 18278), (44, 18167), (30, 18162), (19, 18153), (40, 18152), (52, 18123), (37, 18083), (11, 18068), (51, 17996), (6, 17841)]


Please input big number seed 1: 123
Please input big number seed 2: 321
seeds = 123 321
[(48, 36932), (13, 19246), (2, 19144), (18, 19060), (29, 19047), (42, 18992), (49, 18840), (21, 18830), (47, 18801), (22, 18797), (39, 18768), (20, 18767), (3, 18734), (1, 18698), (52, 18693), (15, 18679), (25, 18675), (5, 18661), (0, 18655), (28, 18629), (7, 18628), (17, 18623), (32, 18613), (8, 18608), (46, 18604), (19, 18593), (33, 18562), (4, 18531), (51, 18497), (9, 18496), (14, 18477), (38, 18476), (36, 18443), (30, 18439), (44, 18408), (23, 18382), (24, 18372), (41, 18371), (43, 18327), (45, 18314), (34, 18269), (11, 18208), (26, 18207), (31, 18164), (35, 18148), (37, 18145), (10, 18133), (50, 18117), (27, 18112), (12, 18063), (40, 18035), (6, 18012), (16, 17975)]

Please input big number seed 1: 88
Please input big number seed 2: 78
seeds = 88 78
[(16, 37746), (7, 19142), (40, 19121), (23, 19050), (38, 18929), (51, 18921), (42, 18904), (1, 18845), (20, 18826), (15, 18761), (39, 18758), (41, 18748), (4, 18746), (6, 18697), (0, 18663), (31, 18652), (11, 18646), (48, 18617), (17, 18580), (22, 18569), (9, 18563), (12, 18559), (24, 18541), (26, 18516), (8, 18509), (45, 18491), (36, 18489), (28, 18474), (32, 18447), (25, 18446), (37, 18438), (50, 18433), (52, 18430), (46, 18394), (49, 18383), (18, 18356), (29, 18356), (14, 18337), (3, 18328), (43, 18318), (33, 18314), (10, 18286), (13, 18261), (19, 18260), (44, 18221), (2, 18219), (47, 18201), (5, 18178), (34, 18175), (21, 18144), (35, 18088), (30, 17964), (27, 17960)]



Notice how the first most common residues stand out:



$(16, 37359)$
$(48, 36932)$
$(16, 37746)$



in each of the three programs runs.



I started out using $\text{mod } 50$ and that pattern was really weird so I tried using the prime number $53$. It works better but still not looking uniform.





Any explanation for this distribution pattern?




My work and motivation



I'm interested in cryptography and was thinking that if two parties shared a secret large number $L$ they could transmit $n$ to represent one of, say, $53$ characters.



So with seeds $= 1,\, 2$ and $(25, 19262)$ counter output, you have $19,262$ different choices for $n$ to transmit the $25^{th}$ character of your 'alphabet'. Of course you can find more $n$ by going past the (artificially} selected one million mark.





Any answers/comments on the strengths and weaknesses of this idea would be appreciated.







Python program (not optimized)



M = 1000000


def bP(i):
p = 1
for j in range(0, i):
p = (p * M)
return p

def getTerm(i):
return ((n1 + n2 * i) * bP(i))

import collections


while True:
print()
n1 = int(input('Please input big number seed 1: '))
n2 = int(input('Please input big number seed 2: '))
print('seeds =',n1,n2)
L = 0
for i in range(0, 499):
L = (L + getTerm(i))
cnt = collections.Counter()

for n in range(1, 1000001):
c = (L % n) % 53
cnt[c] += 1
print(cnt.most_common())

No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...