Félprímek

A Wikipédiából, a szabad enciklopédiából

Félprím (vagy pq szám) minden olyan természetes szám, amely két (nem feltétlenül különböző) prímszám szorzata. Az első néhány félprím a következő:

4, 6, 9, 10, 14, 15, 21, 22, 25, 26, … (A001358 sorozat az OEIS-ben)

2007-ben a legnagyobb ismert félprím a (232 582 657 ‒ 1)2. Ez a legnagyobb ismert prímszám négyzete. Minden prímszám négyzete félprím.

Az Euler-függvény értéke egyszerűen kifejezhető abban az esetben, ha p és q különbözőek:

φ(n) = n + 1 ‒ (p + q).

Alkalmazások [szerkesztés]

A félprímek a számelméletben, különösen kriptográfiai alkalmazásokban a nyílt kulcsú titkosításnál alkalmazzák. Az RSA-eljárásban arra alapul, hogy két nagy prímet találni és összeszorozni viszonylag könnyű, viszont a szorzatot faktorizálni, azaz a félprím ismeretében a szorzat tényezőit meghatározni nehéz.

A gyakorlati kriptográfiában nem elegendő tetszőleges félprímet választani. Léteznek specializált faktorizálóalgoritmusok, amelyek bizonyos alakú félprímeket hatékonyan tudnak faktorizálni, egy jó félprím pedig nehezen faktorizálható. A p és a q tényezők legyenek nagyok, közelítőleg azonos nagyságrendűek, de ne legyenek túl közel egymáshoz.

m • v • sz
Félprímek

4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95, 106, 111, 115, 118, 119, 121, 122, 123, 129, 133, 134, 141, 142, 143, 145, 146, 155, 158, 159, 161, 166, 169, 177, 178, 183, 185, 187, 194, 201, 202, 203, 205, 206, 209, 213, 214, 215, 217, 218, 219, 221, 226, 235, 237, 247, 249, 253, 254, 259, 262, 265, 267, 274, 278, 287, 289, 291, 295, 298, 299, 301, 302, 303, 305, 309, 314, 319, 321, 323, 326, 327, 329, 334, 335, 339, 341, 346, 355, 358, 361, 362, 365, 371, 377, 381, 382, 386, 391, 393, 394, 395, 398, 403, 407, 411, 413, 415, 417, 422, 427, 437, 445, 446, 447, 451, 453, 454, 458, 466, 469, 471, 473, 478, 481, 482, 485, 489, 493, 497, 501, 502, 505, 511, 514, 515, 517, 519, 526, 527, 529, 533, 535, 537, 538, 542, 543, 545, 551, 553, 554, 559, 562, 565, 566, 573, 579, 581, 583, 586, 589, 591, 597, 611, 614, 622, 623, 626, 629, 633, 634, 635, 649, 655, 662, 667, 669, 671, 674, 679, 681, 685, 687, 689, 694, 695, 697, 698, 699, 703, 706, 707, 713, 717, 718, 721, 723, 731, 734, 737, 745, 746, 749, 753, 755, 758, 763, 766, 767, 771, 778, 779, 781, 785, 789, 791, 793, 794, 799, 802, 803, 807, 813, 815, 817, 818, 831, 835, 838, 841, 842, 843, 849, 851, 862, 865, 866, 869, 871, 878, 879, 886, 889, 893, 895, 898, 899, 901, 905, 913, 914, 917, 921, 922, 923, 926, 933, 934, 939, 943, 949, 951, 955, 958, 959, 961, 965, 973, 974, 979, 982, 985, 989, 993, 995, 998,…  · kanonikus alakok listája
P mathematics.svg Ez a matematikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle!
A lap eredeti címe: „http://hu.wikipedia.org/w/index.php?title=Félprímek&oldid=13197434”