Quadratic
Residuosity problem
The quadratic
residuosity problem in computational
number theory is the question of distinguishing by calculating the quadratic residues modulo N,
where N is a composite number.
This is an important consideration in contemporary cryptography.[1]
Quadratic residue modulo
In number theory, an integer
q is called a quadratic residue modulo n if it is congruent to a perfect
square modulo n; i.e., if there exists an integer x
such that:
Otherwise, q is called a quadratic nonresidue modulo n.
A composite number
A composite number
is a positive
integer that has a positive divisor other than
one or itself. In other words a composite number is any positive integer greater than one that is not
a prime number.
The first 105 composite numbers (sequence
4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 99, 100, 102, 104, 105, 106, 108, 110, 111, 112, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 128, 129, 130, 132, 133, 134, 135, 136, 138, 140.
The first 105
composite numbers
are
4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20,
21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46,
48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72,
74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96,
98, 99, 100, 102, 104, 105, 106, 108, 110, 111, 112, 114, 115, 116, 117, 118,
119, 120, 121, 122, 123, 124, 125, 126, 128, 129, 130, 132, 133, 134, 135, 136,
138, 140.
very useful
ReplyDelete