Artifact was a personalized social news aggregator app that uses recommender systems to suggest articles. Launched in January 2023 by Nokto, Inc., a company founded by co-founders of Instagram Kevin Systrom and Mike Krieger, the app is available for iOS and Android. The app's name is a portmanteau of the words "articles", "artificial intelligence", and "fact". The app shut down in January 2024 as a result of low interest. == History == Nokto, Inc. was established on March 3, 2022, as a foreign stock company in California, with its headquarters in San Francisco. The company's main product, Artifact, is the first new product launched by Krieger and Systrom since their 2018 resignation from Instagram after conflicts with parent company Meta, which acquired Instagram in 2012. Artifact launched on January 31, 2023, after the team had been working on it for over a year, offering the option to sign up for a waiting list for its private beta, which grew to about 160,000 people, and then launching in open beta on February 22, 2023. With a team of seven employees in San Francisco, the app was free throughout its lifetime, with the founders explaining at the time that different business models - such as advertising or subscription fees - could be explored in the future. In January 2024, cofounder Kevin Systrom announced that the app would be shutting down after concluding that "the market opportunity isn’t big enough to warrant continued investment in this way." In April 2024, it was announced Artifact had been acquired by Yahoo, who intended to use the service's technology in an upgraded Yahoo! News app. == Features == Frequently described as "TikTok for text" and a competitor to Twitter, Artifact was a news aggregator that used machine learning to make personalized recommendations based on topics, news sources, and authors that the reader is interested in. In addition to reading articles, the app offered the ability to like articles, leave comments, or listen to an audio version of an article read by AI-generated voices, including a simulation of the voices of Snoop Dogg or Gwyneth Paltrow. AI also would rewrite clickbait headlines that users flagged. Artifact later expanded to a social network where users could post links, images and text to their profile, which could be liked or commented on by other users. Similar to other social news websites like Reddit, reader accounts had profiles with reputation scores.
Magisto
Magisto provided an online video editing tool (both as a web application and a mobile app) for automated video editing and production. In 2019, the company was acquired by Vimeo for an estimated US$200 million. The Magisto app contained a library of music. The music, largely by independent artists, was sorted by mood and is licensed for in-app use. Magisto had a freemium business model where users can create basic video clips for free. In addition, advanced business, professional and personal service tiers are available via various subscription plans, unlocking more features; such as longer videos, HD, premium themes, customization, and control features. == History == Magisto was founded in 2009 as SightEra (LTD) by Oren Boiman (CEO) and Alex Rav-Acha (CTO). Boiman, frustrated with the amount of time it took editing together videos of his daughter, wanted an easier to use application to capture and share videos. Boiman, a computer scientist that graduated from Tel Aviv University, followed with graduate work in computer vision at the Weizmann Institute of Science. Boiman developed several patent-pending image analysis technologies that analyze unedited videos to identify the most interesting parts. The system recognized faces, animals, landscapes, action sequences, movements and other important content within the video, as well as analyzing speech and audio. These scenes are then edited together, along with music and effects. Magisto was launched publicly on September 20, 2011, as a video editing software web application through which users could upload unedited video footage, choose a title and soundtrack and have their video edited for them automatically. On the following day, Magisto was added to YouTube Create's collection of video production applications. The Magisto iPhone app was launched publicly at the 2012 International Consumer Electronics Show (CES) in Las Vegas. At CES, the company was also awarded first place in the 2012 CES Mobile App Showdown. In August 2012, Magisto launched the Android app on Google Play. In September 2012, Magisto launched a Google Chrome App and announced Google Drive integration. In March 2013, Magisto claimed it had 5 million users. Google listed Magisto as an "Editors’ Choice" on its list of "Best Apps of 2013". In September 2013, the company claimed that 10 million users had downloaded the App. In February 2014, Magisto claimed that they had 20 million users, with 2 million new users per month. The company also confirmed investment from Mail.Ru. In September 2014, Magisto rolled out a feature called 'Instagram Ready' which allowed users to upload 15 second clips that are automatically formatted for Instagram. In the same month, Magisto launched a feature for iOS and Android users, called 'Surprise Me', which created video from still photography on users’ smartphones. In October 2014, Magisto was placed 9th on the 2014 Deloitte Israel Technology Fast 50 list and named as a finalist in the Red Herring's Top 100 Europe award. In July 2015, Magisto released an editing theme dedicated to Jerry Garcia. In April 2019, the company was acquired by Vimeo, the IAC-owned platform for hosting, sharing and monetizing streamed video, for an estimated $200 million. === Financing === In 2011, the company received more than $5.5 million in a Series B venture round funding from Magma Venture Partners and Horizons Ventures. In September 2011, at the same time as the public launch of their web application, Magisto announced a $5.5 million Series B funding round led by Li Ka-shing’s Horizons Ventures. Li Ka-Shing is known for making early-stage investments in companies like Facebook, Spotify, SecondMarket and Siri. In October 2013, the company received $13 million in funding from Qualcomm and Sandisk. In 2014, the company received $2 million in Venture Funding from Magma Venture Partners, Qualcomm Ventures, Horizons Ventures and the Mail.Ru Group. == Awards == Magisto won first place at Technonomy3, an annual Internet Technology start-up competition in Israel. Judges of the competition included Jeff Pulver, TechCrunch editor Mike Butcher, investor Yaron Samid, Bessemer Venture Partners Israel partner Adam Fisher and Brad McCarty of The Next Web. Magisto won first place at CES 2012 Mobile app competition, during the launch of Magisto iOS mobile app. Magisto was awarded twice the Google Play Editor's Choice and was part of iPhone App Store Best App awards for 2013 and 2014, and Wired Essential iPad Apps. Magisto was declared by Deloitte as the 7th fastest growing company in Europe, the Middle East, and Africa in 2016.
Online public access catalog
The online public access catalog (OPAC), now frequently synonymous with library catalog, is an online database of materials held by a library or group of libraries. Online catalogs have largely replaced the analog card catalogs previously used in libraries. == History == === Early online === Although a handful of experimental systems existed as early as the 1960s, the first large-scale online catalogs were developed at Ohio State University in 1975 and the Dallas Public Library in 1978. These and other early online catalog systems tended to closely reflect the card catalogs that they were intended to replace. Using a dedicated terminal or telnet client, users could search a handful of pre-coordinate indexes and browse the resulting display in much the same way they had previously navigated the card catalog. Throughout the 1980s, the number and sophistication of online catalogs grew. The first commercial systems appeared, and would by the end of the decade largely replace systems built by libraries themselves. Library catalogs began providing improved search mechanisms, including Boolean and keyword searching, as well as ancillary functions, such as the ability to place holds on items that had been checked-out. At the same time, libraries began to develop applications to automate the purchase, cataloging, and circulation of books and other library materials. These applications, collectively known as an integrated library system (ILS) or library management system, included an online catalog as the public interface to the system's inventory. Most library catalogs are closely tied to their underlying ILS system. === Stagnation and dissatisfaction === The 1990s saw a relative stagnation in the development of online catalogs. Although the earlier character-based interfaces were replaced with ones for the Web, both the design and the underlying search technology of most systems did not advance much beyond that developed in the late 1980s. At the same time, organizations outside of libraries began developing more sophisticated information retrieval systems. Web search engines like Google and popular e-commerce websites such as Amazon.com provided simpler to use (yet more powerful) systems that could provide relevancy ranked search results using probabilistic and vector-based queries. Prior to the widespread use of the Internet, the online catalog was often the first information retrieval system library users ever encountered. Now accustomed to web search engines, newer generations of library users have grown increasingly dissatisfied with the complex (and often arcane) search mechanisms of older online catalog systems. This has, in turn, led to vocal criticisms of these systems within the library community itself, and in recent years to the development of newer (often termed 'next-generation') catalogs. === Next-generation catalogs === Newer generations of library catalog systems, typically called discovery systems (or a discovery layer), are distinguished from earlier OPACs by their use of more sophisticated search technologies, including relevancy ranking and faceted search, as well as features aimed at greater user interaction and participation with the system, including tagging and reviews. These new features rely heavily on existing metadata which may be poor or inconsistent, particularly for older records. Newer catalog platforms may be independent of the organization's integrated library system (ILS), instead providing drivers that allow for the synchronization of data between the two systems. While the original online catalog interfaces were almost exclusively built by ILS vendors, libraries have increasingly sought next-generation catalogs built by enterprise search companies and open-source software projects, often led by libraries themselves. == Union catalogs == Although library catalogs typically reflect the holdings of a single library, they can also contain the holdings of a group or consortium of libraries. These systems, known as union catalogs, are usually designed to aid the borrowing of books and other materials among the member institutions via interlibrary loan. Examples of this type of catalogs include COPAC, SUNCAT, NLA Trove, and WorldCat—the last catalogs the collections of libraries worldwide. == Related systems == There are a number of systems that share much in common with library catalogs, but have traditionally been distinguished from them. Libraries utilize these systems to search for items not traditionally covered by a library catalog, although these systems are sometimes integrated into a more comprehensive discovery system. Bibliographic databases—such as Medline, ERIC, PsycINFO, Scopus, Web of Science, and many others—index journal articles and other research data. There are also a number of applications aimed at managing documents, photographs, and other digitized or born-digital items such as Digital Commons and DSpace. Particularly in academic libraries, these systems (often known as digital library systems or institutional repository systems) assist with efforts to preserve documents created by faculty and students. Electronic resource management helps librarians to track selection, acquisition, and licensing of a library's electronic information resources.
Knowledge spillover
Knowledge spillover is an exchange of ideas among individuals. Knowledge spillover is usually replaced by terminations of technology spillover, R&D spillover and/or spillover (economics) when the concept is specific to technology management and innovation economics. In knowledge management economics, knowledge spillovers are non-rival knowledge market costs incurred by a party not agreeing to assume the costs that has a spillover effect of stimulating technological improvements in a neighbor through one's own innovation. Such innovations often come from specialization within an industry. There are two kinds of knowledge spillovers: internal and external. Internal knowledge spillover occurs if there is a positive impact of knowledge between individuals within an organization that produces goods and/or services. An external knowledge spillover occurs when the positive impact of knowledge is between individuals outside of a production organization. Marshall–Arrow–Romer (MAR) spillovers, Porter spillovers and Jacobs spillovers are three types of spillovers. == Conceptualizations == === Marshall–Arrow–Romer === Marshall–Arrow–Romer (MAR) spillover has its origins in 1890, where the English economist Alfred Marshall developed a theory of knowledge spillovers. Knowledge spillovers later were extended by economists Kenneth Arrow (1962) and Paul Romer (1986). In 1992, Edward Glaeser, Hedi Kallal, José Scheinkman, and Andrei Shleifer pulled together the Marshall–Arrow–Romer views on knowledge spillovers and accordingly named the view MAR spillover in 1992. Under the Marshall–Arrow–Romer (MAR) spillover view, the proximity of firms within a common industry often affects how well knowledge travels among firms to facilitate innovation and growth. The closer the firms are to one another, the greater the MAR spillover. The exchange of ideas is largely from employee to employee, in that employees from different firms in an industry exchange ideas about new products and new ways to produce goods. The opportunity to exchange ideas that lead to innovations key to new products and improved production methods. Research on the Cambridge IT Cluster (UK) suggests that technological knowledge spillovers might only happen rarely and are less important than other cluster benefits such as labour market pooling. === Porter === Porter (1990), like MAR, argues that knowledge spillovers in specialized, geographically concentrated industries stimulate growth. He insists, however, that local competition, as opposed to local monopoly, fosters the pursuit and rapid adoption of innovation. He gives examples of Italian ceramics and gold jewellery industries, in which hundreds of firms are located together and fiercely compete to innovate since the alternative to innovation is demise. Porter's externalities are maximized in cities with geographically specialized, competitive industries. === Jacobs === Under the Jacobs spillover view, the proximity of firms from different industries affect how well knowledge travels among firms to facilitate innovation and growth. This is in contrast to MAR spillovers, which focus on firms in a common industry. The diverse proximity of a Jacobs spillover brings together ideas among individuals with different perspectives to encourage an exchange of ideas and foster innovation in an industrially diverse environment. Developed in 1969 by urbanist Jane Jacobs and John Jackson the concept that Detroit’s shipbuilding industry from the 1830s was the critical antecedent leading to the 1890s development of the auto industry in Detroit since the gasoline engine firms easily transitioned from building gasoline engines for ships to building them for automobiles. == Incoming and outgoing spillovers == Knowledge spillover has asymmetric directions. The focal entity and receives or outflows know-how to others, creating incoming and outgoing spillovers. Cassiman and Veugelers (2002) use survey data and estimate incoming and outgoing spillover and study the economic impacts. Incoming spillover increases growth opportunity and productivity improvements of receivers, while outgoing spillover leads to free rider problem in the technology competition. Chen et al. (2013) use econometric method to gauge incoming spillover, a way that applies for all companies without survey. They find that incoming spillover explains R&D profits of industrial firms. == Policy implications == As information is largely non-rival in nature, certain measures must be taken to ensure that, for the originator, the information remains a private asset. As the market cannot do this efficiently, public regulations have been implemented to facilitate a more appropriate equilibrium. As a result, the concept of intellectual property rights have developed and ensure the ability of entrepreneurs to temporarily hold on to the profitability of their ideas through patents, copyrights, trade secrets, and other governmental safeguards. Conversely, such barriers to entry prevent the exploitation of informational developments by rival firms within an industry. For example, Wang (2023) indicates that technology spillovers are reduced by 27% to 51% when trade secrets laws are implemented by the Uniform Trade Secrets Act in the US. On the other hand, when the research and development of a private firm results in a social benefit, unaccounted for within the market price, often greater than the private return of the firm's research, then a subsidy to offset the underproduction of that benefit might be offered to the firm in return for its continued output of that benefit. Government subsidies are often controversial, and while they might often result in a more appropriate social equilibrium, they could also lead to undesirable political repercussions as such a subsidy must come from taxpayers, some of whom may not directly benefit from the researching firm's subsidized knowledge spillover. The concept of knowledge spillover is also used to justify subsidies to foreign direct investment, as foreign investors help diffuse technology among local firms. == Examples == Business parks are a good specific example of concentrated businesses that may benefit from MAR spillover. Many semiconductor firms intentionally located their research and development facilities in Silicon Valley to take advantage of MAR spillover. In addition, the film industry in Los Angeles, California, and elsewhere relies on a geographic concentration of specialists (directors, producers, scriptwriters, and set designers) to bring together narrow aspects of movie-making into a final product. A general example of a knowledge spillover could be the collective growth associated with the research and development of online social networking tools like Facebook, YouTube, and Twitter. Such tools have not only created a positive feedback loop, and a host of originally unintended benefits for their users, but have also created an explosion of new software, programming platforms, and conceptual breakthroughs that have perpetuated the development of the industry as a whole. The advent of online marketplaces, the utilization of user profiles, the widespread democratization of information, and the interconnectivity between tools within the industry have all been products of each tool's individual developments. These developments have since spread outside the industry into the mainstream media as news and entertainment firms have developed their own market feedback applications within the tools themselves, and their own versions of online networking tools (e.g. CNN’s iReport).
Unrestricted algorithm
An unrestricted algorithm is an algorithm for the computation of a mathematical function that puts no restrictions on the range of the argument or on the precision that may be demanded in the result. The idea of such an algorithm was put forward by C. W. Clenshaw and F. W. J. Olver in a paper published in 1980. In the problem of developing algorithms for computing, as regards the values of a real-valued function of a real variable (e.g., g[x] in "restricted" algorithms), the error that can be tolerated in the result is specified in advance. An interval on the real line would also be specified for values when the values of a function are to be evaluated. Different algorithms may have to be applied for evaluating functions outside the interval. An unrestricted algorithm envisages a situation in which a user may stipulate the value of x and also the precision required in g(x) quite arbitrarily. The algorithm should then produce an acceptable result without failure.
UpScrolled
UpScrolled is an Australian social media platform for microblogging and short-form online video sharing that was launched in June 2025 by Recursive Methods Pty Ltd. It was founded by Issam Hijazi. == History == UpScrolled was launched in June 2025 by Recursive Methods Pty Ltd. It was founded by Issam Hijazi, a Palestinian-Australian app developer. UpScrolled is backed by the Tech for Palestine incubator. In January 2026, UpScrolled saw increased attention and number of downloads after the acquisition of TikTok by a group of pro-Donald Trump US investors, including Larry Ellison, which led to calls to boycott TikTok and migrate to other apps. TikTok was alleged to be suppressing pro-Palestinian content, as well as news surrounding the killing of Alex Pretti in Minneapolis on the platform. UpScrolled subsequently climbed to the top 10 of Apple's App Store list of free apps. The app saw a reported 2,850% increase in downloads between 22 and 24 January 2026. As of 27 January 2026, UpScrolled "had been downloaded about 400,000 times in the US and 700,000 globally since launching in June 2025". The app became the most downloaded app in the Apple App store on 29 January 2026, following allegations that TikTok was suppressing videos and content opposed to Immigration and Customs Enforcement (ICE) under its new ownership. By 2 February 2026, UpScrolled had reached 2.5 million users. According to the Google Play Store and the Apple App Store, it has become the most downloaded social media app in the United States and Canada, with rising interest in the United Kingdom, France, Germany and Italy. On 14 February, UpScrolled was suspended from the Google Play Store; the suspension was reverted by 15 February. == Founder == Hijazi was born in Jordan. His parents and grandparents are from Safad, a northern Israeli city near the Lebanese border. He worked for IBM and Oracle prior to starting UpScrolled. Hijazi told Rest of World that he launched UpScrolled in response to Israel's genocide in Gaza which followed the October 7 attacks. He said, "I couldn't take it anymore. I lost family members in Gaza, and I didn't want to be complicit. So I was like, I'm done with this, I want to feel useful. I found this gap in the market, with a lot of people asking why there is no alternative to the Big Tech platforms for their content, which was getting censored." Hijazi also alleges that social media accounts that were posting pro-Palestinian content were getting shadow banned on larger platforms, and alleges that even his account was not exempt from being targeted by censors. Hijazi has further elaborated on the importance of social media independence to further the Palestinian cause. In January 2026, Web Summit Qatar announced that Hijazi would be an opening night speaker. Following the announcement, there was a surge in ticket sales for the summit. Hijazi lives in Sydney with his wife and daughter. He lost 60 family members during the Gaza war. == Features == UpScrolled's algorithm allows users to discover posts based on likes, comments, and shares with time decay and some randomness, all chronologically, with "no manipulation" according to the app's website. UpScrolled has an interface resembling a mix of Instagram and Twitter, allowing users to post and view text posts, photos, and videos. It also lets users send private messages to each other. The app is currently available for iOS and Android devices, with plans to upscale. UpScrolled does not include Israel as an option in its location selection menu. Cities such as Tel Aviv are included under "Occupied Territories of Palestine", and Palestine can also be set as the location. UpScrolled says that it is against censorship and shadow banning, and describes itself as "belong[ing] to the people who use it — not to hidden algorithms or outside agendas". Hijazi said, "The other platforms claim to be free speech platforms. But when it comes to anything on Palestine, that's a different story." UpScrolled states that it "does not tolerate hate speech, propaganda, or bad-faith behaviour, but it also refuses to silence voices quietly or without explanation". == User base and content == Al Jazeera reported that posts expressing pro-Palestinian sentiment or depicting the continued suffering in the Gaza Strip were "flooding" the app. Political and global issues such as the Gaza war are prominent. Content includes updates from the Gaza Freedom Flotilla, posts by doctors working in Gaza, video essays about Palantir’s influence within the military and calls for boycotts of Israel. It has been used by Gazans to crowdfund and record daily life. Celebrity users of UpScrolled include American labour activist Chris Smalls and actor Jacob Berger, both of whom were on the July 2025 Gaza Freedom Flotilla. Political figures have also joined UpScrolled, such as South African politician and Economic Freedom Fighters leader Julius Malema, and Islamic Revolutionary Guard Corps commander Esmail Qaani. One user said that most early users were attracted to the platform for the opportunity to criticize Zionism. The Jewish Telegraphic Agency (JTA) reported that UpScrolled was observed to be "flooded" with antisemitic and anti-Israel content, including Holocaust denial and accusations that Israel carried out the 9/11 attacks. In a statement, UpScrolled said, "Our content moderation hasn't been able to keep up with the massive rise of users this week. We're working with digital rights experts to grow our Trust & Safety team and are beefing up our content moderation to prevent this. We apologise to all impacted users, thank you for being part of Upscrolled." The Times reported in February 2026 that UpScrolled was hosting content that could potentially breach UK law, including antisemitic content and posts promoting Hamas, Hezbollah, Islamic State and Al-Qaeda, as well as footage of the 2019 Christchurch mosque shootings and content praising the perpetrators of the 2019 Halle synagogue shooting and 2018 Pittsburgh synagogue shooting. Antisemitic influencers Lucas Gage, Jake Shields, Stew Peters and Anastasia Maria Loupis have accounts on UpScrolled. UpScrolled’s policies prohibit threats, glorification of harm or support for terrorist or violent groups. Hijazi said harmful content was being uploaded to UpScrolled and the company had expanded its content moderation team and upgraded its technology infrastructure to deal with the issue. In May 2026, Moment magazine said that users had identified some antisemitic content, pornography and extremist videos on the platform. The magazine said there were gaps in content moderation due to the small size of the developer team. == Reception == In January 2026, the Council on American–Islamic Relations (CAIR) praised UpScrolled for "pledging to protect the free flow of ideas on its platform, including both support for and opposition to the Israeli government's human rights abuses." Guy Christensen, a pro-Palestinian social media celebrity, has encouraged his audience to download UpScrolled. Christensen characterized UpScrolled as having "no censorship, no ownership by billionaires who put their interests and biases onto you to control you". He compared the platform to others like TikTok, saying that Israel is behind censorship that wouldn't happen on UpScrolled. Jaigris Hodson, an associate professor of Interdisciplinary Studies at Royal Roads University in Canada, has argued that "Network effects mean that unless UpScrolled continues its explosive growth, people are unlikely to continue to choose it over the more established TikTok. At best, we might see a Twitter/X effect, which is where TikTok will host more pro-U.S. government content creators and those people who want to follow them, and UpScrolled will host more critical content creators and their followers."
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