Wieferich素数

Question

我需要帮助做一件我正在做的工作。任务是编写一个程序来寻找两个给定值之间的所有Wieferich素数。确定它是否为Wieferich素数的公式如下： Wieferich素数p是这样的：p²除以2^（p−1）−1

到目前为止，我的情况是：

start=int(input("enter start value"))
end=int(input("enter end value"))

for c in range(start,end):
  if c%2!=0:
    primedet=(c**2)/((2**(c-1))-1)

    if primedet%1==0:
      print(c," is a Wiefrich Prime")

每次我运行它，它只打印给定值之间的所有奇数。我知道只有两个Wieferich素数：1093和3011。我真的不知道该怎么做。任何指导都将不胜感激。你知道吗

Answer 1

这很简单。根据你的陈述，这些数字的性质是素数prime和Wieferich仅仅通过你给出的等式，所以（2^（p-1）-1）%p²==0返回True意味着你找到了一个数字。如@Copperfield所述，这可以写成（2^（p-1））%p²==1。然后你可以做（在pow的帮助下，速度更快）：

# I assume we have `start` and `end` given by user. Now we can safely
# start from the first odd number greater or equal to start so we can
# stride by 2 in the `range` call which will half our iteration
start = start + 1 if start % 2 == 0 else start
# next I'm using filter because it's faster then the normal `for` loop
# and gives us exactly what we need, that is the list of numbers
# that pass the equation test. Note I've also included the `end`
# number. If I were to write `range(start, end, 2)` we wouldn't
# test for `end`
restult = list(filter(lambda n: pow(2, n - 1, n*n) == 1, range(start, end + 2, 2)))

Answer 2

模运算的使用使这一任务变得更容易，因为您希望2^p-1-1可以被p²整除，也就是说2^p-1-1=0（modp²）重新排列，在python中得到2^p-1=1（modp²）

(2**(p-1)) % (p**2) == 1

但这是低效的，因为首先计算2^p-1然后取模，但别担心，python有一种有效的方法，用pow的3参数调用进行模幂运算

pow(2,p-1,p**2) == 1 

最后，你还需要p是素数，然后实现素数测试，你就可以开始了

def isPrime(n:int) -> bool:
    return True #put here the code for primality check

def find_Wieferich_prime_in(star,end) -> [int]:
    resul = list()
    for p in range(star,end):
        if isPrime(p) and pow(2,p-1,p**2)==1:
            resul.append(p)
    return resul

print(find_Wieferich_prime_in(0,4000))

这就是你找到Wieferich prime所需要的一切

你的另一个错误就在这里

primedet=(c**2)/((2**(c-1))-1)

2^c-1-1总是大于c²（到足够大的c），因此c²/（2^c-1-1）<；1

此外

primedet%1

因为primedet是一个float，当你做float%1时，它会给你这个数字的小数部分，混合四舍五入问题，你会得到太多的零， 但更重要的是，你测试的不是Wieferich素数的定义。你知道吗