我正在为我的编程类做一项python作业。这个问题要求我们接受一些输入,并以a/b mod N的形式表示,返回a/b mod N作为0到n-1之间的整数。下面是我所做的:例如,输入>>> a= 3,b= 2,n=7,接受输入并计算3/2,然后计算1.5mod 7
然而,这不是老师想要的答案。正确的答案是5。我想要做的是在范围(1,n)中找到一个整数,这样一个*整数== 1 mod N,这就是我们想要的。然
考虑一种算法,该算法接受整数N,并将2、3、4的所有因子除以,直到关于sqrt(N)。如果加、减、乘和除数需要单位时间,这个算法有多快?如果要花费Theta(n)时间来加、减、乘和除以两个n-digit二进制数呢?
为了更好地理解这个问题,我首先写了一些伪代码,概述了算法。我想是这样的。N = N / i;
print i # Print the prime factors o