In cryptography, a hybrid cryptosystem is one which combines the convenience of a public-key cryptosystem with the efficiency of a symmetric-key cryptosystem. Public-key cryptosystems are convenient in that they do not require the sender and receiver to share a common secret in order to communicate securely. However, they often rely on complicated mathematical computations and are thus generally much more inefficient than comparable symmetric-key cryptosystems. In many applications, the high cost of encrypting long messages in a public-key cryptosystem can be prohibitive. This is addressed by hybrid systems by using a combination of both. A hybrid cryptosystem can be constructed using any two separate cryptosystems: a key encapsulation mechanism, which is a public-key cryptosystem a data encapsulation scheme, which is a symmetric-key cryptosystem The hybrid cryptosystem is itself a public-key system, whose public and private keys are the same as in the key encapsulation scheme. Note that for very long messages the bulk of the work in encryption/decryption is done by the more efficient symmetric-key scheme, while the inefficient public-key scheme is used only to encrypt/decrypt a short key value. == Implementations and standards == All practical implementations of public key cryptography today employ a hybrid system. Examples include the TLS protocol and the SSH protocol, that use a public-key mechanism for key exchange (such as Diffie-Hellman) and a symmetric-key mechanism for data encapsulation (such as AES). The OpenPGP file format and the PKCS#7 file format are other examples. Hybrid Public Key Encryption (HPKE, published as RFC 9180) is a modern standard for generic hybrid encryption. HPKE is used within multiple IETF protocols, including Messaging Layer Security (MLS), Oblivious DNS over HTTPS, Oblivious HTTP, Privacy Preserving Measurement, and TLS Encrypted Client Hello. Envelope encryption is an example of a usage of hybrid cryptosystems in cloud computing. In a cloud context, hybrid cryptosystems also enable centralized key management. == Example == To encrypt a message addressed to Alice in a hybrid cryptosystem, Bob does the following: Obtains Alice's public key. Generates a fresh symmetric key for the data encapsulation scheme. Encrypts the message under the data encapsulation scheme, using the symmetric key just generated. Encrypts the symmetric key under the key encapsulation scheme, using Alice's public key. Sends both of these ciphertexts to Alice. To decrypt this hybrid ciphertext, Alice does the following: Uses her private key to decrypt the symmetric key contained in the key encapsulation segment. Uses this symmetric key to decrypt the message contained in the data encapsulation segment. == Security == If both the key encapsulation and data encapsulation schemes in a hybrid cryptosystem are secure against adaptive chosen ciphertext attacks, then the hybrid scheme inherits that property as well. However, it is possible to construct a hybrid scheme secure against adaptive chosen ciphertext attacks even if the key encapsulation has a slightly weakened security definition (though the security of the data encapsulation must be slightly stronger). == Envelope encryption == Envelope encryption is term used for encrypting with a hybrid cryptosystem used by all major cloud service providers, often as part of a centralized key management system in cloud computing. Envelope encryption gives names to the keys used in hybrid encryption: Data Encryption Keys (abbreviated DEK, and used to encrypt data) and Key Encryption Keys (abbreviated KEK, and used to encrypt the DEKs). In a cloud environment, encryption with envelope encryption involves generating a DEK locally, encrypting one's data using the DEK, and then issuing a request to wrap (encrypt) the DEK with a KEK stored in a potentially more secure service. Then, this wrapped DEK and encrypted message constitute a ciphertext for the scheme. To decrypt a ciphertext, the wrapped DEK is unwrapped (decrypted) via a call to a service, and then the unwrapped DEK is used to decrypt the encrypted message. In addition to the normal advantages of a hybrid cryptosystem, using asymmetric encryption for the KEK in a cloud context provides easier key management and separation of roles, but can be slower. In cloud systems, such as Google Cloud Platform and Amazon Web Services, a key management system (KMS) can be available as a service. In some cases, the key management system will store keys in hardware security modules, which are hardware systems that protect keys with hardware features like intrusion resistance. This means that KEKs can also be more secure because they are stored on secure specialized hardware. Envelope encryption makes centralized key management easier because a centralized key management system only needs to store KEKs, which occupy less space, and requests to the KMS only involve sending wrapped and unwrapped DEKs, which use less bandwidth than transmitting entire messages. Since one KEK can be used to encrypt many DEKs, this also allows for less storage space to be used in the KMS. This also allows for centralized auditing and access control at one point of access.
Puck App
Puck App is a mobile application that allows hockey players to quickly find and rent a hockey goalie. Founded in 2015 in Toronto, the application primarily operates throughout Canada. It is available on Apple's App Store and Google Play. == History == Puck App was founded in 2016 by Niki Sawni. Users can rate the goalies, message with available goalies, and coordinate skill levels. In 2017, Puck App expanded to Western Canada and has over 1,000 goalies registered. In 2018, Puck App charged approximately $40 CDN to rent a goalie with more than 2 hours notice. Previously, Puck App was a competitor to a similar application called GoalieUp. As of 2024, both companies have agreed to a merger deal.
Virtual facility
A Virtual Facility (VF) is a highly realistic digital representation of a data center, used to model all relevant aspects of a physical data center with a high degree of precision. The term "virtual" in Virtual Facility refers to its use of virtual reality, rather than the abstraction of computer resources as seen in platform virtualization. The VF mirrors the characteristics of a physical facility over time and allows for detailed analysis and modeling. == VF Model features == A standard VF model includes: Three-dimensional physical facility layout Network connectivity of facility equipment Full inventory of facility equipment, including electronics and electrical systems such as power distribution units (PDUs) and uninterruptible power supplies (UPSs) Full air conditioning system (ACUs) and controls within the room The term Virtual Facility was introduced to address the emerging environmental problems facing modern Mission Critical Facilities (MCFs). This concept combines virtual reality (VR), computer simulation, and expert systems applied to the domain of facilities. The VF type of computer simulation allows for detailed analysis and prototyping of airflow in the data center using computational fluid dynamics (CFD) techniques. This enables the visualization and numerical analysis of airflow and temperatures within the facility, helping to predict real-world outcomes. == VF applications == The VF model can be used to assist with the following: Greenfield design Asset management Troubleshooting existing data centers Making existing data centers more resilient Making existing data centers more energy efficient Cost prediction Staff training Capacity planning Load growth management Many organizations use VF models to virtually assess scenarios before committing resources to physical changes. This allows for better decision-making regarding the addition or modification of equipment, helping to avoid logistical or thermal problems.
EdgeRank
EdgeRank is the name commonly given to the algorithm that Facebook uses to determine what articles should be displayed in a user's News Feed. As of 2011, Facebook has stopped using the EdgeRank system and uses a machine learning algorithm that, as of 2013, takes more than 100,000 factors into account. EdgeRank was developed and implemented by Serkan Piantino. == Formula and factors == In 2010, a simplified version of the EdgeRank algorithm was presented as: ∑ e d g e s e u e w e d e {\displaystyle \sum _{\mathrm {edges\,} e}u_{e}w_{e}d_{e}} where: u e {\displaystyle u_{e}} is user affinity. w e {\displaystyle w_{e}} is how the content is weighted. d e {\displaystyle d_{e}} is a time-based decay parameter. User Affinity: The User Affinity part of the algorithm in Facebook's EdgeRank looks at the relationship and proximity of the user and the content (post/status update). Content Weight: What action was taken by the user on the content. Time-Based Decay Parameter: New or old. Newer posts tend to hold a higher place than older posts. Some of the methods that Facebook uses to adjust the parameters are proprietary and not available to the public. A study has shown that it is possible to hypothesize a disadvantage of the "like" reaction and advantages of other interactions (e.g., the "haha" reaction or "comments") in content algorithmic ranking on Facebook. The "like" button can decrease the organic reach as a "brake effect of viral reach". The "haha" reaction, "comments" and the "love" reaction could achieve the highest increase in total organic reach. == Impact == EdgeRank and its successors have a broad impact on what users actually see out of what they ostensibly follow: for instance, the selection can produce a filter bubble (if users are exposed to updates which confirm their opinions etc.) or alter people's mood (if users are shown a disproportionate amount of positive or negative updates). As a result, for Facebook pages, the typical engagement rate is less than 1% (or less than 0.1% for the bigger ones), and organic reach 10% or less for most non-profits. As a consequence, for pages, it may be nearly impossible to reach any significant audience without paying to promote their content.
List of library and information science journals
This list covers the journals, magazines, periodicals already published and continuing in the discipline of library and information science (LIS). It doesn't include ceased titles or predatory journals. Titles listed were taken from various scholarly sources, UGC Care and Wikipedia articles. == LIS journal prestige as assessed by LIS faculty == In a 2013 article by Laura Manzari, 232 LIS faculty members from ALA-accredited information science programs ranked the most prestigious journals in library and information science. The following journals were ranked in the top ten most prestigious: Journal of the Association for Information Science and Technology The Library Quarterly Annual Review of Information Science and Technology Journal of Documentation Library Trends Library and Information Science Research Information Processing and Management Journal of Education for Library and Information Science Education College & Research Libraries First Monday (journal) A subsequent study by Safón and Docampo in 2023 identified impactful LIS journals based on their influence on papers published in other LIS publications. Journals listed in the top ten in this study that did not appear in Manzari's list include: Scientometrics International Journal of Information Management Quantitative Science Studies MIS Quarterly Information and Management Journal of the Association for Information Systems Journal of Informetrics The Journal of Academic Librarianship == India == Annals of Library and Information Studies. (Pub: CSIR-NIScPR ), Formerly: Annals of Library Science. ISSN 0003-4835. (1954-) OPEN ACCESS Collnet Journal of Scientrometrics and Information Management (Pub: Taru Publications, Online through Taylor and Francis) ISSN: 0973-7766 Online 2168-930X. College Libraries (Pub: West Bengal College Librarians’ Association (WBCLA) ISSN 0972-1975, Quarterly DESIDOC Journal of Library and Information Technology (DJLIT) (Formerly: DESIDOC Bulletin 0970-8154, DESIDOC Bulletin of Information Technology. 0971-4383/0974-0643) (Pub: Defence Scientific Information & Documentation Centre) ISSN: 0974-0643, ISSN: 0976-4658 (O), Bi-monthly, OPEN ACCESS. Grandhalaya Sarvaswam (Bilingual: Telugu & English) [Pub: Andhra Pradesh Library Association, Vijayawada, Andhra Pradesh, India] (1915–) Gyankosh: Journal of Library and Information Management. (Pub: Integrated Academy Of Management And Technology. Through: Indian Journals.Com). ISSN: 2229-4023 (P), 2249-3182. Half yearly. IASLIC Bulletin (Pub: Indian Association of Special Libraries and Information Centres) ISSN: 0018-8411. Quarterly (1956-) IASLIC Newsletter (Pub: Indian Association of Special Libraries and Information Centres. (Pub: Indian Association of Special Libraries and Information Centres) ISSN 0018-845X. Monthly. (1966-) INFLIBNET Newsletter. (Pub: INFLIBNET). Monthly. Informatics Studies. (Pub: Centre For Informatics Research And Development). Quarterly. Through: Indian journals.com. ISSN: 2583-8994 (Online), 2320-530X (Print) ISST Journal of Advances in Librarianship (Pub:Intellectuals Society for Socio-Techno Welfare) ISSN: 0976-9021. Semiannual. Journal of Advanced Research in Library and Information Science. (JALIS Publishers). 4/year. ISSN 2277-2219. Journal of Indian Library Association (Pub: Indian Library Association). ISSN (P) 2277-5145 O) 2456-513X. Quarterly. (1965-). Journal of Scientometric Research. (Pub: Phcog.Net). ISSN (P) 2321-6654, (O) 2320-0057]; Frequency : Triannual. KELPRO Bulletin (Pub: Kerala Library Professionals' Organisation - KELPRO). ISSN 0975-4911( Print),2582-497X (O).(1993-) KIIT Journal of Library and Information Management (Pub: KIIT University, online through Indian Journals.com) Half yearly. ISSN: 2348-0858. Library Herald. (Pub: Delhi Library Association - DLA). Quarterly. ISSN: 0024-2292. Library Progress (International). (Pub: Bpas Publications, Through: ). Half yearly. ISSN: 0970-1052. (O) ISSN: 2320-317X. (1981-) Pearl: A Journal of Library and Information Science. (Pub: University Library Teacher's Association of Andhra Pradesh, Hyderabad), ISSN: 0973-7081 (print), 0975-6922 (online). Quarterly. RBU Journal of Library and Information Science. (Pub: Rabindra Bharati University).ISSN: 0972-2750. Annual. SALIS Journal of Information Management and Technology - SJIMT. (Pub: Society for the Advancement of Library and Information Science). Half-yearly. ISSN 0975-4105. SALIS Journal of Library and Information Science - SJLIS: an International Journal. (Pub: Society for the Advancement of Library and Information Science). Half-yearly. ISSN: 0973-3108. SRELS journal of Information and Knowledge (Formerly: Library Science with a Slant to Documentation, ISSN: 0024-2543; Library Science with a Slant to Documentation and Information Studies ISSN: 0970-6089; SRELS Journal of Information Management ISSN: ). Quarterly. ISSN: 2583-9314 (O) World Digital Libraries. Half yearly. ISSN: 0974-567X (P), 0975-7597 (O). == Other countries == African Journal of Library, Archives and Information Science Art Libraries Journal (Cambridge University Press) Bibliothèque de l'École des Chartes Canadian Journal of Information and Library Science Cataloging & Classification Quarterly Communications in Information Literacy Cataloging & Classification Quarterly Catholic Library Association Children and Libraries Code4Lib Journal College & Research Libraries Communications in Information Literacy Disability in Library and Information Studies Electronic Journal of Academic and Special Librarianship El Profesional de la Información (es) (EPI) (Formerly Information World en Español) Evidence Based Library and Information Practice (journal) Faslname-ye Ketab Florida Libraries. Florida Library Association. Georgia Library Quarterly. Quarterly. (Pub: Georgia Library Association). Hipertext.net IFLA Journal In the Library with the Lead Pipe Information & Culture International Journal of Information Retrieval Research (IJIRR) Information Processing and Management Information Research Information Sciences (journal) Information Visualization (journal) Information, Communication & Society International Journal of Geographical Information Science Information Research: An International Electronic Journal (IR) Internet Research (journal) Issues in Science and Technology Librarianship Italian Journal of Library and Information Studies (JLIS.it) JLIS.it Journal of Documentation (JDoc) Journal of Information Ethics Journal of Information Science (JIS) Journal of Information Technology Journal of Informetrics Journal of Librarianship and Information Science Journal of Library & Information Studies - JLIS. (Pub: National Taiwan University) Journal of Library Administration Journal of Religious & Theological Information Journal of the Association for Information Science and Technology (Formerly Journal of the American Society for Information Science and Technology) (JASIST) Journal of the Medical Library Association Journal of the Canadian Health Libraries Association (Pub: Canadian Health Libraries Association). Knowledge Organization (journal) Knowledge Quest. (Pub: American Association of School Librarians) Library and Information Science Abstracts Library Literature and Information Science Library, Information Science & Technology Abstracts Library Literature and Information Science Retrospective Library Review (journal) Library Trends Libri (journal) Malaysian Journal of Library and Information Science MLA Forum New Century Library New Review of Children's Literature and Librarianship Notes (journal) Portal – Libraries and the Academy Progressive Librarian, Progressive Librarians Guild Reference and User Services Quarterly Reference Services Review Research Evaluation (journal) Scientometrics (journal) Serials Review South African Journal of Libraries and Information Science The Charleston Advisor The Christian Librarian, from the Association of Christian Librarians The Journal of Academic Librarianship The Library Quarterly (LQ) The Public-Access Computer Systems Review TripleC Webolog
CHAOS (chess)
CHAOS (Chess Heuristics and Other Stuff) is a chess playing program that was developed by programmers working at the RCA Systems Programming division in the late 1960s. It played competitively in computer chess competitions in the 1970s and 1980s. It differed from other programs of that era in its look-ahead philosophy, choosing to use chess knowledge to evaluate fewer positions and continuations as opposed to simple evaluations that relied on deep look-ahead to avoid bad moves. == Introduction == CHAOS was originally developed by Ira Ruben, Fred Swartz, Victor Berman, Joe Winograd and William Toikka while working at RCA in Cinnaminson, NJ. Its name is an acronym for 'Chess Heuristics and Other Stuff.' Program development moved to the Computing Center of the University of Michigan when Swartz changed jobs, and Mike Alexander joined the development group. Swartz, Alexander and Berman were continuously group members from that point onward in CHAOS' evolution, as others of the original authors left and new members contributed episodically. Chess Senior Master Jack O'Keefe contributed to CHAOS' development from about 1980 onwards. CHAOS was written in Fortran, except for low-level board representation manipulations written in assembly language or C. Due to this portability, it ran on RCA, Univac and IBM-compatible mainframes in its lifetime. CHAOS heralds from the mainframe computing era when only machines of that capacity were able to play at a high level. Consequently, development and testing could only take place at off-peak times for production use of the machine. In a competition, CHAOS had to run on a dedicated mainframe with a telephone link to the match venue. In its later years, CHAOS ran on computers on the machine assembly floor of Amdahl Corporation on MTS. == Background == === Chess and artificial intelligence === Mathematicians Claude Shannon and Alan Turing, working separately, were the first to view playing chess as a challenge to machines. Working for AT&T / Bell Labs with its access to telephone switching equipment, Shannon built a relay-based machine that learned how to work its way through a two-dimensional, 5x5 cell maze in 1949. Shannon viewed this as an analogue of the way that organisms learn things about their natural environment. There is a random element to searching it, a memory element to benefit from the search outcome, and a reward element that reinforces learning when the global outcome is favorable to the organism. Soon afterward, Shannon wrote a mathematical analysis of the game of chess, published in 1950. Like with the maze, he broke down game play into the necessary elements for reinforcement learning. Associated with each board configuration a move will be made from, there is a numerical score. To decide what move to make, a player wants to maximize their own position's score after the move and to minimize their opponent's score (a minimax view). Since there are about 32 possible moves at each of the early stages of the game, and about 40 moves and responses in each game, then there are about 32 80 {\displaystyle 32^{80}} or about 10 120 {\displaystyle 10^{120}} possible games - an impossibly large set to evaluate completely. Therefore, there must be a way to limit the number of moves to look ahead for to find the best one. Reducing the game to these few key elements provided a way to think about human intelligence in general. Shannon became part of a wider group using computing machines to mimic aspects of human intelligence that grew into the general idea of artificial intelligence. (Other members of this group were John McCarthy, Herbert Simon, Allen Newell, Alan Kotok, Alex Bernstein and Richard Greenblatt.) The paradigm that evolved was that there was a quantification of the position on the board into a score, an evaluation method to find favorable outcomes (minimax, later alpha-beta pruning), and a strategy to manage the combinatorial explosion of the look-ahead possibilities. By the early 1960s, there were computer programs that played chess at a rudimentary level. They used very simple evaluation functions for each position and tried to search as far forward as was practical given the time constraints and available compute power. Naturally, programmers optimized their code to use the available computing resources. This led to a major philosophical divide among chess programs: those that tried to evaluate as many positions as possible, and those that tried to evaluate the most promising move sequences as deeply as possible. CHAOS was firmly in the camp believing only the most promising moves should be evaluated in depth. Said Swartz, "The 'brute force people' ... look at every (possible move) no matter what garbage it is. Most moves are just terrible, terrible moves, and most computing time is being spent on pure garbage." The program spent more time evaluating each board position in the expectation that it would find the most promising lines of play to explore in depth. In 1983, the then-fastest chess program (Belle) evaluated 110,000 positions per second, and typical programs 1000–50,000 per second, whereas CHAOS evaluated about 50-100 per second. === Machine learning and strategies to manage search === From about 1949 onward, Arthur Samuel began work for IBM on machine learning, culminating in a checkers-playing program in 1952 and publications on the topic. Concurrently, Christopher Strachey created Checkers, a program to play the board game of checkers in 1951, but it had no capacity to learn from its play. Checkers was chosen by both authors because it was simpler than chess yet contained the basic characteristics of an intellectual activity, and, in Samuel's view, was a test-bed in which heuristic procedures and learning processes could be evaluated quickly. Checker playing programs introduced the notion of the game tree and evaluating play to various depths to choose the best move. The complexity of chess, however, promoted it to the status of an analogue for human intelligence, and it attracted computer scientists' attention, who referred to it as research into artificial intelligence (AI). Like checkers, it required a numerical assessment of each arrangement of chess pieces on a board. It also required looking ahead to future moves to decide how to play the present position. Due to the enormous number of possible moves, there had to be a way to confine the look-ahead search to the most promising lines of play. From these factors, the notion of minimax score evaluation developed and, later, alpha-beta tree pruning to abandon looking at positions worse than any that have already been examined. === Chess search strategies === The AI community viewed artificial intelligence as comprising two parts: a way to symbolically quantify the knowledge in hand (a chess board position), and a set of heuristics to limit look-ahead to the consequences of a move. The early chess playing programs attempted to look forward as far as possible, perhaps to 3 moves ahead by each player, and to choose the best outcome. This led to the horizon effect, whereby a key move 4 or more moves ahead would be unexamined and therefore missed. Consequently, the programs were quite weak and heuristics to manage the search became important in their development. CHAOS used a selective search strategy with iterative widening. As chess programs evolved, they incorporated books of opening lines of play from historic sources. Nowadays, book moves are catalogued in machine-readable form, but originally programmers had to type them in. CHAOS had an extensive book for its time of around 10,000 moves that O'Keefe helped to develop. A problem with play from an opening book is the behavior of the program when the play leaves the book: the positional advantage may be so subtle that the evaluation scheme may be unable to understand it, leading to very wide and shallow searches to establish a line of play. The horizon effect again plagues move selection after leaving the book. CHAOS mitigated these problems by only using book lines that it could understand, and by relying on cached analyses of continuations out of the book made while the opponent's clock was running. == Game Play History == CHAOS played in twelve ACM computer chess tournaments and four World Computer Chess Championships (WCCC). Its debut was the ACM computer chess tournament in 1973, taking 2nd place. In 1974, it again won 2nd place in the WCCC, defeating the tournament favorite Chess 4.0 but losing to Kaissa. CHAOS was close to winning the 1980 WCCC, but lost to Belle in a playoff. The 1985 ACM computer chess tournament was CHAOS' last competition. One of CHAOS' notable victories was over Chess 4.0 at the 1974 WCCC tournament. Chess 4.0 was unbeaten by any other program up until then. Playing as white, CHAOS made a knight sacrifice (16 Nd4-e6!!) that traded material for open lines of attack and eventually won the game. CHAOS’ authors thought the move was due to a
Berlekamp–Rabin algorithm
In number theory, Berlekamp's root finding algorithm, also called the Berlekamp–Rabin algorithm, is the probabilistic method of finding roots of polynomials over the field F p {\displaystyle \mathbb {F} _{p}} with p {\displaystyle p} elements. The method was discovered by Elwyn Berlekamp in 1970 as an auxiliary to the algorithm for polynomial factorization over finite fields. The algorithm was later modified by Rabin for arbitrary finite fields in 1979. The method was also independently discovered before Berlekamp by other researchers. == History == The method was proposed by Elwyn Berlekamp in his 1970 work on polynomial factorization over finite fields. His original work lacked a formal correctness proof and was later refined and modified for arbitrary finite fields by Michael Rabin. In 1986 René Peralta proposed a similar algorithm for finding square roots in F p {\displaystyle \mathbb {F} _{p}} . In 2000 Peralta's method was generalized for cubic equations. == Statement of problem == Let p {\displaystyle p} be an odd prime number. Consider the polynomial f ( x ) = a 0 + a 1 x + ⋯ + a n x n {\textstyle f(x)=a_{0}+a_{1}x+\cdots +a_{n}x^{n}} over the field F p ≃ Z / p Z {\displaystyle \mathbb {F} _{p}\simeq \mathbb {Z} /p\mathbb {Z} } of remainders modulo p {\displaystyle p} . The algorithm should find all λ {\displaystyle \lambda } in F p {\displaystyle \mathbb {F} _{p}} such that f ( λ ) = 0 {\textstyle f(\lambda )=0} in F p {\displaystyle \mathbb {F} _{p}} . == Algorithm == === Randomization === Let f ( x ) = ( x − λ 1 ) ( x − λ 2 ) ⋯ ( x − λ n ) {\textstyle f(x)=(x-\lambda _{1})(x-\lambda _{2})\cdots (x-\lambda _{n})} . Finding all roots of this polynomial is equivalent to finding its factorization into linear factors. To find such factorization it is sufficient to split the polynomial into any two non-trivial divisors and factorize them recursively. To do this, consider the polynomial f z ( x ) = f ( x − z ) = ( x − λ 1 − z ) ( x − λ 2 − z ) ⋯ ( x − λ n − z ) {\textstyle f_{z}(x)=f(x-z)=(x-\lambda _{1}-z)(x-\lambda _{2}-z)\cdots (x-\lambda _{n}-z)} where z {\displaystyle z} is some element of F p {\displaystyle \mathbb {F} _{p}} . If one can represent this polynomial as the product f z ( x ) = p 0 ( x ) p 1 ( x ) {\displaystyle f_{z}(x)=p_{0}(x)p_{1}(x)} then in terms of the initial polynomial it means that f ( x ) = p 0 ( x + z ) p 1 ( x + z ) {\displaystyle f(x)=p_{0}(x+z)p_{1}(x+z)} , which provides needed factorization of f ( x ) {\displaystyle f(x)} . === Classification of === F p {\displaystyle \mathbb {F} _{p}} elements Due to Euler's criterion, for every monomial ( x − λ ) {\displaystyle (x-\lambda )} exactly one of following properties holds: The monomial is equal to x {\displaystyle x} if λ = 0 {\displaystyle \lambda =0} , The monomial divides g 0 ( x ) = ( x ( p − 1 ) / 2 − 1 ) {\textstyle g_{0}(x)=(x^{(p-1)/2}-1)} if λ {\displaystyle \lambda } is quadratic residue modulo p {\displaystyle p} , The monomial divides g 1 ( x ) = ( x ( p − 1 ) / 2 + 1 ) {\textstyle g_{1}(x)=(x^{(p-1)/2}+1)} if λ {\displaystyle \lambda } is quadratic non-residual modulo p {\displaystyle p} . Thus if f z ( x ) {\displaystyle f_{z}(x)} is not divisible by x {\displaystyle x} , which may be checked separately, then f z ( x ) {\displaystyle f_{z}(x)} is equal to the product of greatest common divisors gcd ( f z ( x ) ; g 0 ( x ) ) {\displaystyle \gcd(f_{z}(x);g_{0}(x))} and gcd ( f z ( x ) ; g 1 ( x ) ) {\displaystyle \gcd(f_{z}(x);g_{1}(x))} . === Berlekamp's method === The property above leads to the following algorithm: Explicitly calculate coefficients of f z ( x ) = f ( x − z ) {\displaystyle f_{z}(x)=f(x-z)} , Calculate remainders of x , x 2 , x 2 2 , x 2 3 , x 2 4 , … , x 2 ⌊ log 2 p ⌋ {\textstyle x,x^{2},x^{2^{2}},x^{2^{3}},x^{2^{4}},\ldots ,x^{2^{\lfloor \log _{2}p\rfloor }}} modulo f z ( x ) {\displaystyle f_{z}(x)} by squaring the current polynomial and taking remainder modulo f z ( x ) {\displaystyle f_{z}(x)} , Using exponentiation by squaring and polynomials calculated on the previous steps calculate the remainder of x ( p − 1 ) / 2 {\textstyle x^{(p-1)/2}} modulo f z ( x ) {\textstyle f_{z}(x)} , If x ( p − 1 ) / 2 ≢ ± 1 ( mod f z ( x ) ) {\textstyle x^{(p-1)/2}\not \equiv \pm 1{\pmod {f_{z}(x)}}} then gcd {\displaystyle \gcd } mentioned below provide a non-trivial factorization of f z ( x ) {\displaystyle f_{z}(x)} , Otherwise all roots of f z ( x ) {\displaystyle f_{z}(x)} are either residues or non-residues simultaneously and one has to choose another z {\displaystyle z} . If f ( x ) {\displaystyle f(x)} is divisible by some non-linear primitive polynomial g ( x ) {\displaystyle g(x)} over F p {\displaystyle \mathbb {F} _{p}} then when calculating gcd {\displaystyle \gcd } with g 0 ( x ) {\displaystyle g_{0}(x)} and g 1 ( x ) {\displaystyle g_{1}(x)} one will obtain a non-trivial factorization of f z ( x ) / g z ( x ) {\displaystyle f_{z}(x)/g_{z}(x)} , thus algorithm allows to find all roots of arbitrary polynomials over F p {\displaystyle \mathbb {F} _{p}} . === Modular square root === Consider equation x 2 ≡ a ( mod p ) {\textstyle x^{2}\equiv a{\pmod {p}}} having elements β {\displaystyle \beta } and − β {\displaystyle -\beta } as its roots. Solution of this equation is equivalent to factorization of polynomial f ( x ) = x 2 − a = ( x − β ) ( x + β ) {\textstyle f(x)=x^{2}-a=(x-\beta )(x+\beta )} over F p {\displaystyle \mathbb {F} _{p}} . In this particular case problem it is sufficient to calculate only gcd ( f z ( x ) ; g 0 ( x ) ) {\displaystyle \gcd(f_{z}(x);g_{0}(x))} . For this polynomial exactly one of the following properties will hold: GCD is equal to 1 {\displaystyle 1} which means that z + β {\displaystyle z+\beta } and z − β {\displaystyle z-\beta } are both quadratic non-residues, GCD is equal to f z ( x ) {\displaystyle f_{z}(x)} which means that both numbers are quadratic residues, GCD is equal to ( x − t ) {\displaystyle (x-t)} which means that exactly one of these numbers is quadratic residue. In the third case GCD is equal to either ( x − z − β ) {\displaystyle (x-z-\beta )} or ( x − z + β ) {\displaystyle (x-z+\beta )} . It allows to write the solution as β = ( t − z ) ( mod p ) {\textstyle \beta =(t-z){\pmod {p}}} . === Example === Assume we need to solve the equation x 2 ≡ 5 ( mod 11 ) {\textstyle x^{2}\equiv 5{\pmod {11}}} . For this we need to factorize f ( x ) = x 2 − 5 = ( x − β ) ( x + β ) {\displaystyle f(x)=x^{2}-5=(x-\beta )(x+\beta )} . Consider some possible values of z {\displaystyle z} : Let z = 3 {\displaystyle z=3} . Then f z ( x ) = ( x − 3 ) 2 − 5 = x 2 − 6 x + 4 {\displaystyle f_{z}(x)=(x-3)^{2}-5=x^{2}-6x+4} , thus gcd ( x 2 − 6 x + 4 ; x 5 − 1 ) = 1 {\displaystyle \gcd(x^{2}-6x+4;x^{5}-1)=1} . Both numbers 3 ± β {\displaystyle 3\pm \beta } are quadratic non-residues, so we need to take some other z {\displaystyle z} . Let z = 2 {\displaystyle z=2} . Then f z ( x ) = ( x − 2 ) 2 − 5 = x 2 − 4 x − 1 {\displaystyle f_{z}(x)=(x-2)^{2}-5=x^{2}-4x-1} , thus gcd ( x 2 − 4 x − 1 ; x 5 − 1 ) ≡ x − 9 ( mod 11 ) {\textstyle \gcd(x^{2}-4x-1;x^{5}-1)\equiv x-9{\pmod {11}}} . From this follows x − 9 = x − 2 − β {\textstyle x-9=x-2-\beta } , so β ≡ 7 ( mod 11 ) {\displaystyle \beta \equiv 7{\pmod {11}}} and − β ≡ − 7 ≡ 4 ( mod 11 ) {\textstyle -\beta \equiv -7\equiv 4{\pmod {11}}} . A manual check shows that, indeed, 7 2 ≡ 49 ≡ 5 ( mod 11 ) {\textstyle 7^{2}\equiv 49\equiv 5{\pmod {11}}} and 4 2 ≡ 16 ≡ 5 ( mod 11 ) {\textstyle 4^{2}\equiv 16\equiv 5{\pmod {11}}} . == Correctness proof == The algorithm finds factorization of f z ( x ) {\displaystyle f_{z}(x)} in all cases except for ones when all numbers z + λ 1 , z + λ 2 , … , z + λ n {\displaystyle z+\lambda _{1},z+\lambda _{2},\ldots ,z+\lambda _{n}} are quadratic residues or non-residues simultaneously. According to theory of cyclotomy, the probability of such an event for the case when λ 1 , … , λ n {\displaystyle \lambda _{1},\ldots ,\lambda _{n}} are all residues or non-residues simultaneously (that is, when z = 0 {\displaystyle z=0} would fail) may be estimated as 2 − k {\displaystyle 2^{-k}} where k {\displaystyle k} is the number of distinct values in λ 1 , … , λ n {\displaystyle \lambda _{1},\ldots ,\lambda _{n}} . In this way even for the worst case of k = 1 {\displaystyle k=1} and f ( x ) = ( x − λ ) n {\displaystyle f(x)=(x-\lambda )^{n}} , the probability of error may be estimated as 1 / 2 {\displaystyle 1/2} and for modular square root case error probability is at most 1 / 4 {\displaystyle 1/4} . == Complexity == Let a polynomial have degree n {\displaystyle n} . We derive the algorithm's complexity as follows: Due to the binomial theorem ( x − z ) k = ∑ i = 0 k ( k i ) ( − z ) k − i x i {\textstyle (x-z)^{k}=\sum \limits _{i=0}^{k}{\binom {k}{i}}(-z)^{k-i}x^{i}} , we may transition from f ( x ) {\displaystyle f(x)} to f ( x − z ) {\displaystyle f(x-z)} in O ( n 2 ) {\displaystyle O(n^{2})} time. Polynomial multiplication a