素数计算装置及方法、以及密钥发行系统

摘要

提供一种计算能够确认是否是合法地生成的素数的素数计算装置。素数计算装置生成随机数，将上述随机数乘以管理标识符来计算乘法运算值R，对于满足2×w×素数q+1＝验证值(mod管理信息)的w，通过N＝2×(乘法运算值R+w)×素数q+1，计算出素数候补N。接着，判断所计算出的素数候补N是否是素数，在判断为素数的情况下，将计算出的素数候补N作为素数输出。

主权项

1、一种素数计算装置，计算大于已知的素数q的素数候补N，来进行素数判断，其特征在于，具备：信息存储单元，存储有已知的素数q、与要生成的素数对应的奇数的管理信息及规定的验证值；随机数生成单元，生成随机数；候补计算单元，读出素数q、上述管理信息及上述验证值，将上述随机数乘以上述管理信息而计算出乘法运算值R，对于满足2×w×素数q+1＝验证值(mod管理信息)的w，通过N＝2×(乘法运算值R+w)×素数q+1，来计算素数候补N；素数判断单元，判断所计算出的素数候补N是否是素数；输出单元，在判断为是素数的情况下，将计算出的素数候补N作为素数输出。