### Jacobi Symbol Parity Checking Algorithm for Subset Product

##### Abstract

It is well-known that the subset product problem is NP-hard. We give a probabilistic polynomial time algorithm for the special case of high F_2-rank.

Note: This is the 2nd paper of the series.

Available format(s)
Category
Foundations
Publication info
Preprint.
Keywords
Subset product Jacobi symbol Parity checking Algorithm Characteristic matrix Rank
Contact author(s)
treyquantum @ gmail com
History
2022-10-03: approved
See all versions
Short URL
https://ia.cr/2022/1308

CC BY

BibTeX

@misc{cryptoeprint:2022/1308,
author = {Trey Li},
title = {Jacobi Symbol Parity Checking Algorithm for Subset Product},
howpublished = {Cryptology ePrint Archive, Paper 2022/1308},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1308}},
url = {https://eprint.iacr.org/2022/1308}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.