Paper Abstract and Keywords |
Presentation |
2023-07-24 18:20
Implementation of Shor's algorithm for the discrete logarithm problem and experiments using the quantum computer simulator Kaito Kishi, Junpei Yamaguchi, Tetsuya Izu (Fujitsu Research), Noboru Kunihiro (Univ. of Tsukuba) ISEC2023-32 SITE2023-26 BioX2023-35 HWS2023-32 ICSS2023-29 EMM2023-32 |
Abstract |
(in Japanese) |
(See Japanese page) |
(in English) |
Classical polynomial-time algorithms for solving the discrete logarithm problem (DLP) over a prime field have not been found yet, and many cryptosystems are constructed based on them.
However, a quantum polynomial-time algorithm for it was given by Shor. Previous quantum simulates to estimate resources for solving DLP are still lacking. In this study, we estimated that 8194 qubits and $1.04times 10^{15}$ quantum gates are required to solve DLP of a 2048 bits characteristic with Q-ADD by simulating quantum circuits solving 1860 patterns of DLP. We also found a type of DLP which are more difficult than other types of them to solve in quantum computers. |
Keyword |
(in Japanese) |
(See Japanese page) |
(in English) |
discrete logarithm problem / quantum computation / quantum circuit simulation / Shor's algorithm / safe prime / DSA / / |
Reference Info. |
IEICE Tech. Rep., vol. 123, no. 129, ISEC2023-32, pp. 119-126, July 2023. |
Paper # |
ISEC2023-32 |
Date of Issue |
2023-07-17 (ISEC, SITE, BioX, HWS, ICSS, EMM) |
ISSN |
Online edition: ISSN 2432-6380 |
Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
Download PDF |
ISEC2023-32 SITE2023-26 BioX2023-35 HWS2023-32 ICSS2023-29 EMM2023-32 |
Conference Information |
Committee |
EMM BioX ISEC SITE ICSS HWS IPSJ-CSEC IPSJ-SPT |
Conference Date |
2023-07-24 - 2023-07-25 |
Place (in Japanese) |
(See Japanese page) |
Place (in English) |
Hokkaido Jichiro Kaikan |
Topics (in Japanese) |
(See Japanese page) |
Topics (in English) |
|
Paper Information |
Registration To |
ISEC |
Conference Code |
2023-07-EMM-BioX-ISEC-SITE-ICSS-HWS-CSEC-SPT |
Language |
Japanese |
Title (in Japanese) |
(See Japanese page) |
Sub Title (in Japanese) |
(See Japanese page) |
Title (in English) |
Implementation of Shor's algorithm for the discrete logarithm problem and experiments using the quantum computer simulator |
Sub Title (in English) |
|
Keyword(1) |
discrete logarithm problem |
Keyword(2) |
quantum computation |
Keyword(3) |
quantum circuit simulation |
Keyword(4) |
Shor's algorithm |
Keyword(5) |
safe prime |
Keyword(6) |
DSA |
Keyword(7) |
|
Keyword(8) |
|
1st Author's Name |
Kaito Kishi |
1st Author's Affiliation |
Fujitsu Research (Fujitsu Research) |
2nd Author's Name |
Junpei Yamaguchi |
2nd Author's Affiliation |
Fujitsu Research (Fujitsu Research) |
3rd Author's Name |
Tetsuya Izu |
3rd Author's Affiliation |
Fujitsu Research (Fujitsu Research) |
4th Author's Name |
Noboru Kunihiro |
4th Author's Affiliation |
Faculty of Engineering, Information and Systems, University of Tsukuba (Univ. of Tsukuba) |
5th Author's Name |
|
5th Author's Affiliation |
() |
6th Author's Name |
|
6th Author's Affiliation |
() |
7th Author's Name |
|
7th Author's Affiliation |
() |
8th Author's Name |
|
8th Author's Affiliation |
() |
9th Author's Name |
|
9th Author's Affiliation |
() |
10th Author's Name |
|
10th Author's Affiliation |
() |
11th Author's Name |
|
11th Author's Affiliation |
() |
12th Author's Name |
|
12th Author's Affiliation |
() |
13th Author's Name |
|
13th Author's Affiliation |
() |
14th Author's Name |
|
14th Author's Affiliation |
() |
15th Author's Name |
|
15th Author's Affiliation |
() |
16th Author's Name |
|
16th Author's Affiliation |
() |
17th Author's Name |
|
17th Author's Affiliation |
() |
18th Author's Name |
|
18th Author's Affiliation |
() |
19th Author's Name |
|
19th Author's Affiliation |
() |
20th Author's Name |
|
20th Author's Affiliation |
() |
Speaker |
Author-1 |
Date Time |
2023-07-24 18:20:00 |
Presentation Time |
20 minutes |
Registration for |
ISEC |
Paper # |
ISEC2023-32, SITE2023-26, BioX2023-35, HWS2023-32, ICSS2023-29, EMM2023-32 |
Volume (vol) |
vol.123 |
Number (no) |
no.129(ISEC), no.130(SITE), no.131(BioX), no.132(HWS), no.133(ICSS), no.134(EMM) |
Page |
pp.119-126 |
#Pages |
8 |
Date of Issue |
2023-07-17 (ISEC, SITE, BioX, HWS, ICSS, EMM) |
|