Алгоритм COS

Алгоритм COS (Копперсмит, Одлыжко, Шреппель) — субэкспоненциальный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Был предложен в 1986 году.

Исходные данные

Пусть задано сравнение

a^{x}\equiv b{\pmod {p}},

((1))

Необходимо найти натуральное число x, удовлетворяющее сравнению (1).

Описание алгоритма

1 этап. Пусть

H:=[p^{1/2}]+1,\ J:=H^{2}-p>0,\ L=e^{\sqrt {\log {p}\log {\log {p}}}},\ 0<\epsilon <1.

Сформируем множество

\{q\mid q<L^{1/2}\}\cup \{H+c|0<c<L^{1/2+\epsilon }\},

где q — простые.

2 этап. С помощью некоторого просеивания ищем пары $c_{1},\ c_{2}$ — такие, что $0<c_{i}<L^{1/2+\epsilon }$ , и

(H+c_{1})(H+c_{2})\equiv \prod \limits _{q\leq L^{1/2}}q^{\alpha _{q}(c_{1},c_{2})}{\pmod {p}}

(рассматривается абсолютно наименьший вычет). При этом так как $J=O(p^{1/2})$ , то

(H+c_{1})(H+c_{2})\equiv J+(c_{1}+c_{2})H+c_{1}c_{2}{\pmod {p}},

причём это абсолютно наименьший вычет в этом классе и он имеет величину $O(p^{1/2+\epsilon })$ . Поэтому вероятность его гладкости выше, чем для произвольных чисел, меньших p-1.

Логарифмируя по основанию a, получим соотношение

\log _{a}{(H+c_{1})}+\log _{a}{(H+c_{2})}\equiv \sum \limits _{q\leq L^{1/2}}\alpha _{q}(c_{1},c_{2})\log _{a}q{\pmod {p-1}}

Мы можем также считать, что a является гладким, то есть

a\equiv \prod \limits _{q\leq L^{1/2}}q^{\beta _{q}}{\pmod {p}},

откуда

1\equiv \sum \limits _{q\leq L^{1/2}}\beta _{q}\log _{a}q{\pmod {p-1}}

3 этап. Набрав на 2-м этапе достаточно много уравнений, мы решим получившуюся систему линейных уравнений и найдём $\log _{a}{(H+c)},\ \log _{a}q$ .

4 этап. Для нахождения x введём новую границу гладкости $L^{2}$ . Случайным перебором находим одно значение w, удовлетворяющее соотношению

a^{w}b\equiv \prod \limits _{q\leq L^{1/2}}q^{\gamma _{q}}\prod \limits _{L^{1/2}\leq u<L^{2}}u^{h_{u}}{\pmod {p}}.

u — простые числа «средней» величины.

5 этап. С помощью методов, аналогичных этапам 2 и 3, мы находим логарифмы простых чисел u, возникших на этапе 4.

6 этап. Находим ответ:

x\equiv \log _{a}b\equiv -w+\sum \limits _{q\leq L^{1/2}}\gamma _{q}\log _{a}q+\sum \limits _{L^{1/2}\leq u<L^{2}}h_{u}\log _{a}u{\pmod {p-1}}.

Оценка сложности

Данный алгоритм имеет сложность $O(\exp {((\log {p}\log {\log {p}})^{1/2})})$ арифметических операций. Предполагается, что для чисел $p<10^{90}$ данный алгоритм более эффективен, чем решето числового поля.

Литература

Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4.

Joux A., Lercier R. Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the gaussian integer method (англ.) // Math. Comp.^[англ.] : journal. — 2003. — Vol. 72. — P. 953—967. — doi:10.1090/S0025-5718-02-01482-5.

Это заготовка статьи по математике. Помогите Википедии, дополнив её.

Read other articles:

Vertical jump

Jump vertically in the air The vertical jump measurement test is designed to measure an athlete's ability to perform powerfully. The measurement method seen here is an improved version of the chalk on finger method. The device used is known as a vertical jump tester. A vertical jump or vertical leap is the act of jumping upwards into the air. It can be an exercise for building both endurance and strength, and is also a standard test for measuring athletic performance.[1] It may also b...

CK Hutchison Holdings

Artikel ini menggunakan kata-kata yang berlebihan dan hiperbolis tanpa memberikan informasi yang jelas. Silakan buang istilah-istilah yang hiperbolis tersebut. (Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini) CK Hutchison Holdings LimitedJenisPublikpKode emitenSEHK: 1IndustriKonglomeratPendahuluCheung Kong HoldingsHutchison WhampoaDidirikan1950 (sebagai Cheung Kong Holdings)18 Maret 2015 (sebagai CK Hutchison Holdings)KantorpusatCheung Kong Center, Pulau Hong Kong, Hong Kon...

Nicolae Ciucă

Nicolae Ciucă Perdana Menteri Rumania ke-70Masa jabatan25 November 2021 – 12 Juni 2023PresidenKlaus IohannisWakilKelemen HunorSorin Grindeanu PendahuluFlorin CîțuPenggantiCătălin Predoiu (Penjabat)Pelaksana tugas7 Desember 2020 – 23 Desember 2020PresidenKlaus IohannisWakilRaluca Turcan PendahuluLudovic OrbanPenggantiFlorin CîțuMenteri Pertahanan NasionalMasa jabatan4 November 2019 – 25 November 2021Perdana MenteriLudovic OrbanDiri sendiriFlorin Cî�...

WTEL (AM)

Radio station in Philadelphia This article is about a radio station in Philadelphia, Pennsylvania. For other stations that have held the same call sign, see WTEL. WTELPhiladelphia, PennsylvaniaBroadcast areaGreater PhiladelphiaFrequency610 kHzBrandingPhiladelphia's BIN 610ProgrammingFormatBlack-oriented newsAffiliationsBlack Information NetworkOwnershipOwnerBeasley Broadcast Group(Beasley Media Group Licenses, LLC)OperatoriHeartMedia, Inc.Sister stationsWBEN-FM, WMGK, WMMR, WPEN, WTMR, WWDB,...

Monsieur Beaucaire (opera)

Monsieur Beaucaire: Act II sword fight Monsieur Beaucaire is a romantic opera in three acts, composed by André Messager.[1] The libretto, based on the 1900 novel by Booth Tarkington,[2] is by Frederick Lonsdale, with lyrics by Adrian Ross. The piece premiered at the Prince of Wales Theatre in Birmingham, England, on 7 April 1919, before opening at the Prince's Theatre in London under the management of Frank Curzon on 19 April 1919 and transferring to the Palace Theatre on 29 ...

Lavender Town

Fictional town in Pokémon universe Lavender TownLavender Town as it appears in Pokémon Red and BlueFirst appearancePokémon Red and BlueLast appearancePokémon: Let's Go, Pikachu! and Let's Go, Eevee!GenreJapanese role-playing gameIn-universe informationOther name(s)Home of SpiritsTypeVillageLocationKanto Lavender Town (Japanese: シオンタウン, Hepburn: Shion Taun, Shion Town) is a fictional village in the 1996 video games Pokémon Red and Blue. Stylized as a haunted location, Lavender...

Ukraina

UkrainaУкраїна (Ukraina) Bendera Lambang Lagu kebangsaan: Державний Гімн УкраїниDerzhavnyi Himn UkrainyLagu Negara UkrainaLokasi Ukraina (green)Wilayah pendudukan Rusia sebelum serangan 2022 (hijau muda) Ibu kota(dan kota terbesar)Kyiv49°N 32°E / 49°N 32°E / 49; 32Koordinat: 49°N 32°E / 49°N 32°E / 49; 32Bahasa resmiUkrainaBahasa daerahyang diakui BelarusBulgariaTatar KrimeaGagauzYunaniIbr...

Hellyeah

American heavy metal supergroup For other uses, see Hell Yeah (disambiguation). HellyeahHellyeah performing in 2013Background informationOriginDallas, Texas, U.S.Genres Groove metal heavy metal alternative metal Years active2006–2021 (indefinite hiatus)Labels Eleven Seven Epic Past members Chad Gray Christian Brady Tom Maxwell Kyle Sanders Roy Mayorga Vinnie Paul Greg Tribbett Bob Zilla Jerry Montano Websitehellyeahband.com Hellyeah, stylized as HELLYEAH, was an American heavy metal supergr...

Loránd Győry

Hungarian politician (1871–1926) The native form of this personal name is Győry Loránd. This article uses Western name order when mentioning individuals. Loránd GyőryMinister of Agriculture of HungaryIn office7 August 1919 – 15 August 1919Preceded byJózsef TakácsSucceeded byIstván Szabó de Nagyatád Personal detailsBorn(1871-04-11)11 April 1871Orosháza, Kingdom of Hungary, Austria-HungaryDied30 July 1926(1926-07-30) (aged 55)Budapest, Kingdom of HungaryPolitical...

Truck Eagan

American baseball player Baseball player Truck EaganInfielderBorn: (1877-08-10)August 10, 1877San Francisco, CaliforniaDied: March 19, 1949(1949-03-19) (aged 71)San Francisco, CaliforniaBatted: RightThrew: RightMLB debutMay 1, 1901, for the Pittsburgh PiratesLast MLB appearanceMay 30, 1901, for the Cleveland BluesMLB statisticsBatting average.133Home runs0Runs batted in4 Teams Pittsburgh Pirates (1901) Cleveland Blues (1901) Charles Eugene Truck Eagan (Augus...

阿苏塞纳

阿苏塞纳Açucena市镇阿苏塞纳在巴西的位置坐标：19°04′22″S 42°32′45″W / 19.0728°S 42.5458°W / -19.0728; -42.5458国家巴西州米纳斯吉拉斯州面积 • 总计811.49 平方公里（313.32 平方英里）人口 • 總計11,127人 • 密度13.7人/平方公里（35.5人/平方英里）阿苏塞纳（葡萄牙语：Açucena）是巴西米纳斯吉拉斯州的一个市镇。总面积811.49平方�...

Johan Pehrson

Swedish politician (born 1968) Johan PehrsonPehrson in 2022Minister for EmploymentIncumbentAssumed office 18 October 2022Prime MinisterUlf KristerssonPreceded byEva NordmarkMinister for IntegrationIncumbentAssumed office 18 October 2022Prime MinisterUlf KristerssonPreceded byAnders YgemanLeader of the LiberalsIncumbentAssumed office 8 April 2022Preceded byNyamko SabuniLeader of the Liberalsin the RiksdagIn office28 June 2019 – 8 April 2022LeaderNyamko SabuniPreceded by...

Douglas Rovers F.C.

Former association football club in Scotland Football clubDouglas RoversFull nameDouglas Rovers Football ClubNickname(s)the RoversFounded1883Dissolved1894GroundBalmoral ParkHon. PresidentsMr M. J. Stewart MP, A. Young, J. W. Hutchison, W. K. Thornhill, and Major Spurgin[1]PresidentMr J. DunnSecretaryWilliam M Haugh Home colours Douglas Rovers F.C. was an association football club from Castle Douglas in Dumfriesshire. History 1889–90 Law Cup 2nd Round, Douglas Rovers 2a0 Excelsior, K...

Southern Baptist Convention

Christian denomination Southern Baptist ConventionAbbreviationSBC; GCBClassificationProtestantOrientationBaptistTheologyEvangelical FundamentalistPolityCongregationalPresidentBart BarberRegionUnited StatesOriginMay 8–12, 1845 Augusta, Georgia, U.S.Separated fromTriennial Convention (1845)SeparationsAmerican Baptist AssociationAlliance of BaptistsCooperative Baptist FellowshipCongregations47,198 (2022)Members12,982,090 (2023) Weekly attendance = 3,800,000 (2022)Missionary organizationInterna...

List of governors of Delaware

Governor of DelawareGreat Seal of the State of DelawareIncumbentJohn Carneysince January 17, 2017Government of DelawareStyleThe HonorableResidenceDelaware Governor's MansionDover, DelawareTerm lengthFour years, renewable onceInaugural holderJohn McKinlyFormationFebruary 12, 1777DeputyLieutenant Governor of DelawareSalary$171,000 (2013)[1]Websitegovernor.delaware.gov The governor of Delaware (known as the president of Delaware from 1776 to 1792) is the head of government of Delaw...

Ryan Trecartin

American artist and filmmaker (born January 26, 1981) Ryan TrecartinTrecartin in 2009Born1981 (age 42–43)Webster, Texas, U.S.EducationRhode Island School of DesignKnown for Video art sculpture installation art new media art Notable workA Family Finds Entertainment 2004I-Be AREA 2007Trill-ogy Comp 2009Any Ever 2010Center Jenny 2013 Ryan Trecartin (born 1981) is an American artist and filmmaker currently based in Athens, Ohio.[1] He studied at the Rhode Island School of ...

Rat bike

Type of motorcycle Rat bikes at the UK Rat and Survival Bike rally, 2005 Rat bikes are motorcycles that have fallen apart over time and have been kept on the road and maintained for little or no cost by employing kludge fixes and improvised repairs, with little or no consideration given to appearance.[1][2] Rat-Look bikes are motorcycles that have been deliberately styled to look like ratbikes. Survival bikes, often confused with rat bikes, may look similar but are different i...

Strategia della tensione

In alto: l'interno della Banca Nazionale dell'Agricoltura di Milano, luogo della strage di piazza Fontana del 1969, dopo l'esplosione che uccise 17 persone e ne ferì 88.In basso: l'ala Ovest della stazione di Bologna Centrale, crollata a seguito dell'esplosione dell'ordigno che nel 1980 causò la morte di 85 persone e il ferimento di oltre 200.Alle due stragi vengono convenzionalmente fatti ricondurre, rispettivamente, l'inizio e la fine della strategia della tensione in Italia. La strategia...

Березняк, Александр Яковлевич

В Википедии есть статьи о других людях с фамилией Березняк. Александр Яковлевич Березняк Дата рождения 16 (29) декабря 1912(1912-12-29) Место рождения дер. Бояркино, Коломенский уезд[1], Московская губерния Дата смерти 7 июля 1974(1974-07-07) (61 год) Место смерти Дубна, Московская о...

Chongqing Rail Transit

Metro ChongqingInfoPemilikChongqing City Transportation Development & Investment (Group) Co., Ltd.WilayahChongqing, TiongkokJenis angkutan cepat straddle-beam monorailJumlah jalur8Jumlah stasiun181Penumpang harian2.036 juta (2017)[1] 3.356 juta (2019)[2]Penumpang tahunan743.10 juta (2017)[1]Pimpinan utamaLe MeiKantor pusat123 Renming Rd., Yuzhong District, ChongqingSitus webhttp://www.cqmetro.cnOperasiDimulai6 November 2004; 19 tahun lalu (2004-11-06) (trial)1...

PROFILPELAJAR.COM