给定一个正整数 a ，求正整数 b（0＜b＜a）使得 a mod b 减去 a mod (b+1) 取到最大值

王守恩

王守恩 发表于 2021-10-14 15:41
给定一个正整数 a ，求正整数 b（0＜b＜a）使得 a mod b 减去 a mod (b+1) 取到最大值
竖一个最大值靶子， ...

一般的数，也是有规律的。

01:                  1, 1,
02:                  2, 2,
03:               1,2, 3,
04:               2,2, 1,3,
05:               3,2, 2,3,
06:               4,2, 3,3,
07:            1,4,2, 4,3,
08:            2,4,2, 5,3,
09:            3,4,2, 1,5,3,
10:            4,4,2, 2,5,3,
11:            5,4,2, 3,5,3,
12:            6,4,2, 4,5,3,
13:         1,6,4,2, 5,5,3,
14:         2,6,4,2, 6,5,3,
15:         3,6,4,2, 7,5,3,
16:         4,6,4,2, 1,7,5,3,
17:         5,6,4,2, 2,7,5,3
18:         6,6,4,2, 3,7,5,3,
19:         7,6,4,2, 4,7,5,3,
20:         8,6,4,2, 5,7,5,3,
21:      1,8,6,4,2, 6,7,5,3,
22:      2,8,6,4,2, 7,7,5,3,
23:      3,8,6,4,2, 8,7,5,3,
24:      4,8,6,4,2, 9,7,5,3,
25:      5,8,6,4,2, 1,9,7,5,3
26:      6,8,6,4,2, 2,9,7,5,3,
27:      7,8,6,4,2, 3,9,7,5,3,
28:      8,8,6,4,2, 4,9,7,5,3,
29:      9,8,6,4,2, 5,9,7,5,3,
30:    10,8,6,4,2, 6,9,7,5,3,
31: 1,10,8,6,4,2, 7,9,7,5,3,
32: 2,10,8,6,4,2, 8,9,7,5,3,
33: 3,10,8,6,4,2, 9,9,7,5,3,

王守恩

王守恩 发表于 2021-10-15 15:10
一般的数，也是有规律的。

01:                  1, 1,

譬如：
.........
\(14:a=14^2-1=195=13\)
  2:196,197=10
  6:198,199,200,201,202,203=11
  4:204,205,206,207=12
  2:208.209=13
  6:210,211,212,213,214,215=11
  5:216,217,218,219,220=12
  3:221,222,223=13
\(15:a=15^2-1=224=14\)      
  3:225,226,227=11
  6:228,229,230,231,232,233=12
  4:234,235,236,237=13
  2:238,239=14
  7:240,241,242,243,244,245,246=12
  5:247,248,249,250,251=13
  3:252,253,254=14
\(16:a=16^2-1=255=15\)
......
要搞个通项公式也是可以的。

王守恩

王守恩 发表于 2021-10-16 11:41
譬如：
.........
\(14:a=14^2-1=195=13\)

接12楼，要搞个通项公式也是可以的。
{0, 1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 2, 3, 2, 2, 3, 3, 2, 3, 3, 3, 4, 3, 3, 3, 4, 4, 3, 3,
4, 4, 4, 5, 4, 4, 4, 4, 5, 5, 4, 4, 4, 5, 5, 5, 6, 4, 5, 5, 5, 5, 6, 6, 5, 5, 5, 5, 6, 6,
6, 7, 5, 5, 6, 6, 6, 6, 7, 7, 6, 6, 6, 6, 6, 7, 7, 7, 8, 6, 6, 6, 7, 7, 7, 7, 8, 8, 6, 7,
7, 7, 7, 7, 8, 8, 8, 9, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 10, 8,
8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 11, 9, 9, 9, 9, 9,
9, 10, 10,  10, 10, 11, 11, 9, 9, 9, 9, 10, 10, 10, 10,  10, 11, 11, 11, 12, 9, ....}

王守恩

王守恩 发表于 2021-10-14 15:41
给定一个正整数 a ，求正整数 b（0＜b＜a）使得 a mod b 减去 a mod (b+1) 取到最大值
竖一个最大值靶子， ...

    平平淡淡才是真。\(a(n)=\mod(n^2-1,n)-\mod(n^2-1,n+1)=n-1\)
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27,
28, 29, 30, 31,32, 33, 34, 35, 36, 37, 38, 39, 40,41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52,
53, 54, 55, 56, 57, 58, 59, 60, 61,62, 63, 64, 65, 66, 67, 68, 69, 70,71, 72, 73, 74, 75, 76, 77,
78, 79, 80, 81,  82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92,  93, 94, 95, 96, 97, 98, 99, 100,.....}

xyaoy

还是没看懂最后得出的结论


这个问题，我其实是想请教两个质数相乘结果为a，那么a mod b 和 a mod (b+1)余数之差的最大值和较小质数是否有关系？
如果有关系，利用这种关系求解RSA私钥是否可行？会比数域筛所需时间更短么？

xyaoy

王守恩 发表于 2021-10-16 19:55
平平淡淡才是真。\(a(n)=\mod(n^2-1,n)-\mod(n^2-1,n+1)=n-1\)
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...

是这样     将原本的问题特例化，a=b*c      b和c都是质数 b<c    取一整数d 0<d<a     计算 （a mod d） -（a mod （d+1））的最大值 e     请问e和b是否有关？

主要是最近碰到个RSA的问题，解不出来不甘心，所以就混到数学论坛求助一下
反正大概率解不出来，碰碰运气吧