We revisit the problem of integer factorization with number-theoretic oracles, including a well-known problem: can we factor an integer $N$ unconditionally, in deterministic polynomial time, given the value of the Euler totient $$\Phi$(N)$? We show that this can be done, under certain size conditions on the prime factors of N. The key technique is lattice basis reduction using the LLL algorithm. Among our results, we show for example that if $N$ is a squarefree integer with a prime factor $p > $\sqrt$ N$ , then we can recover p in deterministic polynomial time given $$\Phi$(N)$. We also shed some light on the analogous problems for Carmichael's function, and the order oracle that is used in Shor's quantum factoring algorithm.


翻译:我们用数字理论或手腕重新审视整数因子化的问题,包括一个众所周知的问题:鉴于Euler Tent $\Phi$(N)的价值,我们能否在确定性多元时间中无条件地将整数纳美元乘以整数因子化的问题?我们显示,在N的质因子的一定规模条件下,可以做到这一点。关键技术是使用LLL算法降低拉特基数。例如,我们显示,如果美元是一个无正方形的整数,其质因子值大于$/sqrt$(N),那么我们可以在确定性多元时恢复p,给$\Phi$(N)。我们还就Carmichael功能的类似问题以及Shor量量因子算法中使用的顺序问题做了一些说明。

0
下载
关闭预览

相关内容

专知会员服务
28+阅读 · 2021年8月2日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
已删除
将门创投
8+阅读 · 2018年10月31日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Many Proxy Controls
Arxiv
0+阅读 · 2021年10月8日
VIP会员
相关VIP内容
专知会员服务
28+阅读 · 2021年8月2日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
已删除
将门创投
8+阅读 · 2018年10月31日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员