Mathematica 2.0 for SPARC
Copyright 1988-91 Wolfram Research, Inc.
 -- Terminal graphics initialized -- 

In[1]:= <<Numbers.m

Quotient::shdw: Warning: Symbol Quotient appears in multiple contexts 
    {Numbers`, System`}; definitions in context Numbers`
     may shadow or be shadowed by other definitions.
Package Numbers` loaded
0.5 Second

In[2]:= Numbers`NTrace[s__]:=Print[s]
0. Second

In[3]:= CycleIndices[x0_, next_, equal_] receives functions next[x_] and equal[x_,y_] 
   and returns the lengths of the pre-period and period of the sequence  {x0,
   next[x0], next[next[x0]], ...}. Equality is determined be the equal  function
   argument.

In[3]:=                             
0. Second

In[4]:= PollardRho[N_Integer?Positive] demonstrates the Pollard rho integer factoring 
   algorithm. A factor is printed (twice), but cylce indices are returned.

In[4]:=                         n = Prime[100]
0. Second

Out[4]= 541

In[5]:= next[x_]:=Mod[x^2+1, n]
0. Second

In[6]:= eq[x_,y_]:=x == y;
0. Second

In[7]:= (* Compute the cycle length for next and eq
using the prime n; should be of order Sqrt[n]. *)\
CycleIndices[3, next, eq]
X = 10, Y = 101
X = 101, Y = 520
X = 464, Y = 64
X = 520, Y = 344
X = 442, Y = 148
X = 64, Y = 437
X = 310, Y = 10
X = 344, Y = 464
X = 399, Y = 442
X = 148, Y = 310
X = 265, Y = 399
X = 437, Y = 265
X = 538, Y = 538
n = 12
0.183333 Second

Out[7]= {1, 13}

In[8]:= (* The same for a different prime *)\
n = Prime[101]
0. Second

Out[8]= 547

In[9]:= CycleIndices[3, next, eq]
X = 10, Y = 101
X = 101, Y = 380
X = 356, Y = 50
X = 380, Y = 57
X = 540, Y = 478
X = 50, Y = 213
X = 313, Y = 415
X = 57, Y = 225
X = 515, Y = 403
X = 478, Y = 214
X = 386, Y = 375
X = 213, Y = 22
X = 516, Y = 16
X = 415, Y = 410
X = 468, Y = 47
X = 225, Y = 485
X = 302, Y = 257
X = 403, Y = 172
X = 498, Y = 22
X = 214, Y = 16
X = 396, Y = 410
X = 375, Y = 47
X = 47, Y = 485
X = 22, Y = 257
X = 485, Y = 172
X = 16, Y = 22
X = 257, Y = 16
X = 410, Y = 410
n = 27
0.35 Second

Out[9]= {23, 7}

In[10]:= (* Now try the Pollard rho idea for composite
moduli; observe the shorted cylce is found.*)\
PollardRho[Prime[100] Prime[101]]
X = 10, Y = 101
X = 101, Y = 210428
X = 10202, Y = 198611
X = 210428, Y = 75543
X = 90248, Y = 266320
X = 198611, Y = 217919
X = 148003, Y = 111456
X = 75543, Y = 71335
X = 88582, Y = 151922
X = 266320, Y = 8966
X = 38676, Y = 2563
X = 217919, Y = 170139
X = 101164, Y = 47605
GCD =541
n = 12
GCD =541
GCD =541
0.25 Second

Out[10]= {1, 13}

In[11]:= (* The same for a larger n. *)\
n = Prime[1000]
0. Second

Out[11]= 7919

In[12]:= CycleIndices[3, next, eq]
X = 10, Y = 101
X = 101, Y = 1388
X = 2283, Y = 6691
X = 1388, Y = 3104
X = 2228, Y = 4654
X = 6691, Y = 7462
X = 3375, Y = 3280
X = 3104, Y = 5085
X = 5313, Y = 723
X = 4654, Y = 5777
X = 1252, Y = 4082
X = 7462, Y = 5648
X = 2956, Y = 2206
X = 3280, Y = 7118
X = 4399, Y = 2813
X = 5085, Y = 4772
X = 1691, Y = 5143
X = 723, Y = 6064
X = 76, Y = 3087
X = 5777, Y = 2996
X = 3064, Y = 6954
X = 4082, Y = 443
X = 1149, Y = 6001
X = 5648, Y = 5346
X = 2173, Y = 2117
X = 2206, Y = 1484
X = 4171, Y = 6701
X = 7118, Y = 4566
X = 163, Y = 2330
X = 2813, Y = 1746
X = 1889, Y = 1696
X = 4772, Y = 2259
X = 4860, Y = 4247
X = 5143, Y = 5236
X = 990, Y = 6243
X = 6064, Y = 4394
X = 4180, Y = 4410
X = 3087, Y = 847
X = 3013, Y = 3910
X = 2996, Y = 2561
X = 3790, Y = 4825
X = 6954, Y = 2309
X = 4703, Y = 4688
X = 443, Y = 4328
X = 6194, Y = 7913
X = 6001, Y = 1370
X = 4309, Y = 1686
X = 5346, Y = 2030
X = 46, Y = 3754
X = 2117, Y = 5347
X = 7455, Y = 1725
X = 1484, Y = 4309
X = 775, Y = 46
X = 6701, Y = 7455
X = 2672, Y = 775
X = 4566, Y = 2672
X = 5549, Y = 5549
n = 56
0.85 Second

Out[12]= {46, 57}

In[13]:= n = Prime[1001]
0.0166667 Second

Out[13]= 7927

In[14]:= CycleIndices[3, next, eq]
X = 10, Y = 101
X = 101, Y = 7222
X = 2275, Y = 4529
X = 7222, Y = 3044
X = 5552, Y = 3895
X = 4529, Y = 5886
X = 4693, Y = 3875
X = 3044, Y = 5322
X = 7201, Y = 2606
X = 3895, Y = 5408
X = 6675, Y = 2950
X = 5886, Y = 1670
X = 4007, Y = 2514
X = 3875, Y = 2934
X = 1888, Y = 6394
X = 5322, Y = 1130
X = 514, Y = 7586
X = 2606, Y = 7421
X = 5725, Y = 2960
X = 5408, Y = 5988
X = 3762, Y = 2690
X = 2950, Y = 882
X = 6582, Y = 6900
X = 1670, Y = 2474
X = 6524, Y = 4872
X = 2514, Y = 4745
X = 2378, Y = 2379
X = 2934, Y = 208
X = 7562, Y = 2227
X = 6394, Y = 2722
X = 3698, Y = 3300
X = 1130, Y = 2309
X = 654, Y = 7026
X = 7586, Y = 6595
X = 5304, Y = 3545
X = 7421, Y = 6982
X = 2373, Y = 5954
X = 2960, Y = 3323
X = 2266, Y = 362
X = 5988, Y = 817
X = 2324, Y = 7048
X = 2690, Y = 4334
X = 6677, Y = 5968
X = 882, Y = 5614
X = 1079, Y = 7209
X = 6900, Y = 1558
X = 439, Y = 6855
X = 2474, Y = 5339
X = 1033, Y = 7821
X = 4872, Y = 987
X = 2947, Y = 2845
X = 4745, Y = 3329
X = 2346, Y = 420
X = 2379, Y = 1134
X = 7691, Y = 363
X = 208, Y = 393
X = 3630, Y = 2131
X = 2227, Y = 3426
X = 5155, Y = 5537
X = 2722, Y = 4942
X = 5467, Y = 5942
X = 3300, Y = 3386
X = 6230, Y = 4105
X = 2309, Y = 7158
X = 4538, Y = 696
X = 7026, Y = 3836
X = 3248, Y = 4567
X = 6595, Y = 2002
X = 6504, Y = 7244
X = 3545, Y = 4496
X = 2731, Y = 4109
X = 6982, Y = 5962
X = 5202, Y = 1278
X = 5954, Y = 1279
X = 573, Y = 2759
X = 3323, Y = 5242
X = 19, Y = 4077
X = 362, Y = 3101
X = 4213, Y = 1185
X = 817, Y = 7655
X = 1622, Y = 4405
X = 7048, Y = 3720
X = 3723, Y = 2076
X = 4334, Y = 3157
X = 4494, Y = 2431
X = 5968, Y = 3947
X = 1014, Y = 3819
X = 5614, Y = 2463
X = 7172, Y = 7340
X = 7209, Y = 3337
X = 270, Y = 6200
X = 1558, Y = 4474
X = 1703, Y = 5203
X = 6855, Y = 1362
X = 7697, Y = 276
X = 5339, Y = 6688
X = 7357, Y = 4547
X = 7821, Y = 4197
X = 3310, Y = 1747
X = 987, Y = 5299
X = 7076, Y = 4649
X = 2845, Y = 2426
X = 559, Y = 1652
X = 3329, Y = 350
X = 296, Y = 2280
X = 420, Y = 2459
X = 2007, Y = 5252
X = 1134, Y = 2506
X = 1783, Y = 1219
X = 363, Y = 5928
X = 4938, Y = 4204
X = 393, Y = 4494
X = 3837, Y = 1014
X = 2131, Y = 7172
X = 6918, Y = 270
X = 3426, Y = 1703
X = 5517, Y = 7697
X = 5537, Y = 7357
X = 4661, Y = 3310
X = 4942, Y = 7076
X = 278, Y = 559
X = 5942, Y = 296
X = 507, Y = 2007
X = 3386, Y = 1783
X = 2555, Y = 4938
X = 4105, Y = 3837
X = 6151, Y = 6918
X = 7158, Y = 5517
X = 4764, Y = 4661
X = 696, Y = 278
X = 870, Y = 507
X = 3836, Y = 2555
X = 2385, Y = 6151
X = 4567, Y = 4764
X = 1553, Y = 870
X = 2002, Y = 2385
X = 4870, Y = 1553
X = 7244, Y = 4870
X = 6724, Y = 6724
n = 138
1.91667 Second

Out[14]= {84, 139}

In[15]:= PollardRho[Prime[1000] Prime[1001]]
X = 10, Y = 101
X = 101, Y = 41306892
X = 10202, Y = 17840279
X = 41306892, Y = 31449453
X = 28098840, Y = 55683143
X = 17840279, Y = 1567505
X = 14392198, Y = 38648000
X = 31449453, Y = 23310702
X = 60910342, Y = 37370484
X = 55683143, Y = 8217780
X = 2479899, Y = 32511577
X = 1567505, Y = 19636849
X = 38196293, Y = 31084281
X = 38648000, Y = 4148755
X = 57417149, Y = 19998288
X = 23310702, Y = 19303375
X = 9013513, Y = 36820574
X = 37370484, Y = 22203021
X = 49335446, Y = 55055975
X = 8217780, Y = 59815203
X = 46392566, Y = 4227781
X = 32511577, Y = 7412627
X = 49550332, Y = 38349799
X = 19636849, Y = 2848267
X = 3541966, Y = 36508707
X = 31084281, Y = 20313719
X = 9625756, Y = 19978419
X = 4148755, Y = 51398876
X = 522817, Y = 55031461
X = 19998288, Y = 61809541
X = 53138379, Y = 29800893
X = 19303375, Y = 47033200
X = 51248709, Y = 36487080
X = 36820574, Y = 6506735
X = 42811104, Y = 18370404
X = 22203021, Y = 28829554
X = 56720058, Y = 61249956
X = 55055975, Y = 28936873
X = 24282667, Y = 34902943
X = 59815203, Y = 1728903
X = 17148425, Y = 5651072
X = 4227781, Y = 52924986
X = 13744168, Y = 61511561
X = 7412627, Y = 14424827
X = 28609622, Y = 704785
X = 38349799, Y = 31202230
X = 50915560, Y = 49812196
X = 2848267, Y = 20266751
X = 38256735, Y = 35211628
X = 36508707, Y = 4321202
X = 35856768, Y = 61666978
X = 20313719, Y = 32361343
X = 37679377, Y = 15323311
X = 19978419, Y = 14111194
X = 34268185, Y = 31795560
X = 51398876, Y = 57185771
X = 56832293, Y = 19082420
GCD =7919
n = 56
GCD =7919
GCD =7919
1.41667 Second

Out[15]= {46, 57}

In[16]:= (* An example where the indices agree for
both factors *)\
PollardRho[31 47]
X = 10, Y = 101
X = 101, Y = 10
X = 3, Y = 3
GCD =1457
n = 2
GCD =1457
GCD =1457
0.0666667 Second

Out[16]= {0, 3}

In[17]:=