Blum integer - Blum integer
v matematika, a přirozené číslo n je Blum integer -li n = p × q je semiprime pro který p a q jsou odlišné prvočísla shodný s 3 mod 4.[1] To znamená p a q musí mít formu 4t + 3, pro celé číslo t. Celá čísla této formy se označují jako Blum prvočísla.[2] To znamená, že faktory Blumova čísla jsou Gaussovy prvočísla bez imaginární části. Prvních několik celých čísel Blum je
- 21, 33, 57, 69, 77, 93, 129, 133, 141, 161, 177, 201, 209, 213, 217, 237, 249, 253, 301, 309, 321, 329, 341, 381, 393, 413, 417, 437, 453, 469, 473, 489, 497, ... (sekvence A016105 v OEIS )
Celá čísla byla pojmenována pro počítačového vědce Manuel Blum.
Vlastnosti
Dáno n = p×q celé číslo Blum, Qn soubor všech kvadratické zbytky modulo n a coprime na n a A ∈ Qn. Pak:[2]
- A má čtyři odmocniny modulo n, přesně jeden z nich je také v Qn
- Unikátní druhá odmocnina z A v Qn se nazývá hlavní odmocnina z A modulo n
- Funkce F: Qn → Qn definován F(X) = X2 mod n je obměna. Inverzní funkce F je: F −1(X) = X((p − 1)(q − 1) + 4)/8 mod n.[3]
- Pro každé celé číslo Blum n, -1 má Jacobi symbol mod n +1, i když -1 není kvadratickým zbytkem n:
Dějiny
Před moderními factoringovými algoritmy, jako např MPQS a NFS, byly považovány za užitečné vybrat celá čísla Blum jako RSA moduly. To již není považováno za užitečné opatření, protože MPQS a NFS jsou schopny faktorovat celá čísla Blum se stejnou lehkostí jako moduly RSA vytvořené z náhodně vybraných prvočísel.
Reference
- ^ Joe Hurd, Blum Integers (1997), získaný 17. ledna 2011 z http://www.gilith.com/research/talks/cambridge1997.pdf
- ^ A b Goldwasser, S. a Bellare, M. „Poznámky k přednášce o kryptografii“. Letní kurz kryptografie, MIT, 1996-2001
- ^ Menezes, Alfred; van Oorschot, Paul; Vanstone, Scott (1997). Příručka aplikované kryptografie. Boca Raton: CRC Press. str.102. ISBN 0849385237. OCLC 35292671.