问题标签 [number-theory]

我想计算：

a ^{b c d 。. .} 模数

你知道任何有效的方法，因为这个数字太大但是 a ， b ， c ， ... 和 m 适合一个简单的 32 位 int。

有任何想法吗？

警告：这个问题与寻找^b mod m 不同。

另请注意， a ^{b c}与 (a ^b ) ^c不同。后者等于 a ^bc。求幂是右结合的。

我想在 Python 中采用像 [[1,2],[3,4]] mod 7 这样的矩阵的模逆。我看过 numpy （它进行矩阵求逆但不进行模矩阵求逆）并且我在网上看到了一些数论包，但似乎没有任何东西可以执行这个相对常见的过程（至少，它对我来说似乎相对常见）。

顺便说一下，上述矩阵的逆矩阵是 [[5,1],[5,3]] (mod 7)。不过，我希望 Python 为我做这件事。

为什么此代码返回一个数字的因子之和？

在几个 Project Euler 问题中，您被要求计算因子的总和作为问题的一部分。在那里的一个论坛上，有人发布了以下 Java 代码作为找到该总和的最佳方法，因为您实际上不必找到单个因素，只需找到主要因素（您不需要了解 Java，您可以跳到我下面的总结）：

现在，我已经尝试了很多次，我发现它有效。问题是，为什么？

说你因素100： 1,2,4,5,10,20,25,50,100。总和是217。素数分解是2*2*5*5。这个功能给你[5*(5+1)+1]*[2*(2+1)+1] = [25+5+1]*[4+2+1] = 217

保理8：1,2,4,8。总和是15。素数分解是2*2*2。这个功能给你[2*(2*(2+1)+1)+1]=15

该算法归结为（Fi用于表示因子 F 或 F sub i 的第 i 个索引）：

其中m是唯一素因子Ni的数量，是每个唯一因子在素因子分解中出现的次数。

为什么这个公式等于因子之和？我的猜测是它等于通过分配属性的主要因素的每个独特组合（即每个独特因素）的总和，但我不知道如何。

这是问题（四个素数的总和）指出：

输入的每一行都包含一个整数 N (N<=10000000)。这是您必须表示为四个素数之和的数字

样本输入：
24
36
46

样本输出：
3 11 3 7
3 7 13 13
11 11 17 7

第一眼就想到了这个想法

• 找到 N 以下的所有素数
• 使用整数分区问题（背包）查找列表的长度（.length = 4）

但我认为这种算法的复杂性非常糟糕。这个问题看起来也更像哥德巴赫的_猜想 。我怎么解决这个问题？

一种方法是对自然数 (1,.., n ) 进行因式分解，看看它们是否有任何重复的素因数，但是对于大的n会花费很多时间。那么有没有更好的方法可以从 1,.., n中获取无平方数？

我可以使用两个循环来检查两个小于p素数的整数的所有组合，但这非常低效。有没有更好的算法来解决这个问题？任何的想法？

哪里p mod 4 = 1。

谢谢，

你将如何生成一个非常非常大的随机数？我正在考虑 2^10^9（十亿位）的数量级。任何编程语言——我认为解决方案会翻译成其他语言。

我想要 [1,N] 上的均匀分布。

我最初的想法：

--您可以随机生成每个数字并连接。问题：即使是非常好的伪随机生成器也可能产生数百万位数的模式，对吧？

• 您也许可以通过将随机数提高到随机指数来帮助创建大随机数。问题：您必须进行数学运算，以使结果数字仍然是随机的，并且您应该能够在合理的时间内（例如，一个小时）计算它。

• 如果有帮助，您可以尝试在可能较小的范围内生成可能不均匀的分布（例如，使用实数）并进行变换。问题：这可能同样困难。

有任何想法吗？

经过反复试验，我找到了以下几行python代码，

产生以下输出，

即 2 到2**(N-1)1 的幂，并且 2 的幂相反。这正是我的问题所需要的（fft 和小波相关）。但是，我不太确定它为什么有效？我理解的最终模运算，它提供了系列中间的 1。第一个模运算中的因子 3 让我很头疼。任何人都可以提供解释吗？具体来说，我的基数 2 和因子 3 之间的关系是什么？

我正在尝试解决欧拉问题 78，它基本上要求分区函数p(n) 可被 1000000 整除的第一个数字。

我使用基于五边形数的欧拉递归公式（此处pents与正确的符号一起计算）。这是我的代码：

虽然ps似乎产生了正确的结果，但它太慢了。有没有办法加快计算速度，还是我需要一种完全不同的方法？

我有点陷入群论的深渊，我对我的密码学课程有点迷茫。基本上我必须在java中实现的一个实用程序是，

顺序（质数，p-1 的因子列表，任意 a）

这应该返回组 Z*p 中 a 的顺序，其中 f 是 p-1 的素因子列表。确保您的方法在 f 包含重复项时有效。例如，考虑 p=17 的情况

这是我到目前为止所拥有的，（取自我笔记中的步骤）

素数 f 的列表由另一种方法生成，然后传入

我的笔记很难理解，我想知道是否有人能告诉我我应该返回什么。你也可以让我对这个群论片段有一个可能的理解，因为它可以帮助我进一步的实践