# Journal of theKorean Mathematical SocietyJKMS

ISSN(Print) 0304-9914 ISSN(Online) 2234-3008

## Article

HOME ALL ARTICLES View

J. Korean Math. Soc. 2022; 59(3): 621-634

Published online May 1, 2022 https://doi.org/10.4134/JKMS.j210446

## On the scaled inverse of $(x^i-x^j)$ modulo cyclotomic polynomial of the form $\Phi_{p^s}(x)$ or $\Phi_{p^s q^t}(x)$

Jung Hee Cheon, Dongwoo Kim, Duhyeong Kim, Keewoo Lee

Seoul National University; Western Digital Research; Intel Labs; Seoul National University

### Abstract

The scaled inverse of a nonzero element $a(x)\in \mathbb{Z}[x]/f(x)$, where $f(x)$ is an irreducible polynomial over $\mathbb{Z}$, is the element $b(x)\in \mathbb{Z}[x]/f(x)$ such that $a(x)b(x)=c \pmod{f(x)}$ for the smallest possible positive integer scale $c$. In this paper, we investigate the scaled inverse of $(x^i-x^j)$ modulo cyclotomic polynomial of the form $\Phi_{p^s}(x)$ or $\Phi_{p^s q^t}(x)$, where $p, q$ are primes with \$p

Keywords: Cyclotomic polynomial, scaled inverse, zero-knowledge proof

MSC numbers: Primary 11C08, 94A60

Supported by: This work was supported by Samsung Electronics Co., Ltd(IO201209-07883-01). This work was done while Duhyeong Kim and Dongwoo Kim were at Seoul National University.