• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>SOFSEM 2009: Theory and practice of computer science >Factoring and Testing Primes in Small Space
【24h】

Factoring and Testing Primes in Small Space

机译：在小空间中分解和测试素数

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We discuss how much space is sufficient to decide whether a unary number n is a prime. We show that O(log log n) space is sufficient for a deterministic Turing machine, if it is equipped with an additional pebble movable along the input tape, and also for an alternating machine, if the space restriction applies only to its accepting computation subtrees. That is, un-Primes is in pebble-DSPACE(log log n) and also in accept-ASPACE(log log n), where un-Primes = {1~n : n is a prime}. Moreover, if the given n is composite, such machines are able to find a divisor of n. Since O(log log n) space is too small to write down a divisor which might require Ω(log n) bits, the witness divisor is indicated by the input head position at the moment when the machine halts.
机译：我们讨论多少空间足以决定一元数n是否为质数。我们证明，O（log log n）空间对于确定性图灵机是足够的，如果它配备有沿输入磁带可移动的附加卵石，并且对于交替机，如果空间限制仅适用于其接受的计算子树，则该空间也足够。也就是说，un-Primes在pebble-DSPACE（log log n）和accept-ASPACE（log log n）中，其中un-Primes = {1〜n：n是素数}。此外，如果给定的n是合成的，则此类机器能够找到n的除数。由于O（log log n）空间太小，无法记下可能需要Ω（log n）位的除数，因此在机器停止时输入头的位置指示见证除数。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号