An Airborne Network (AN) is the infrastructure owned by the United States Air Force that provides communication transport services through at least one node that is on a platform capable of flight. == Background == === Definition === The intent of the US Air Force's Airborne Network is to expand the Global Information Grid (GIG) to connect the three major domains of warfare: Air, Space, and Terrestrial. The Transformational Satellite Communications System network currently provides connectivity for all communication through space assets. The Combat Information Transport System and Theater Deployable Communications provide terrestrial connectivity for theatre based operations. The Airborne Network is engineered to utilize all airborne assets to connect with space and surface networks building a seamless communications platform across all domains. === Capabilities === The capabilities identified by this type of system are vastly beyond that of our current military. This system will enable the Air Force to provide a transportable network, flexible enough to communicate with any air, space, or ground asset in the area. The network will provide a beyond line-of-sight (LoS) communications infrastructure that can be packed up and moved in and out of the designated battlespace, enabling the military to have a reliable and secure communications network that extends globally. The network is designed to be flexible enough to provide the right communication and network packages for a specific region, mission, or technology. Operationally, The AN is designed to be self-forming, self-organizing, and self-generating, with nodes joining and leaving the network as they enter and exit a specific region. The network consists of dedicated tactical links, wideband air-to-air links, and ad hoc networks constructed by the Joint Tactical Radio System (JTRS) networking services. JTRS is a software-defined radio that will work with many existing military and civilian radios. It includes integrated encryption and Wideband Networking Software to create mobile ad hoc networks. It also provides system performance analysis and fault diagnostics automatically, reducing the demand for human intervention and network maintenance. === Intended Use === The AN was designed as the cornerstone for the new military doctrine known as Network Centric Warfare. This doctrine was developed to use information superiority to equip warfighters with more precise information enabling commanders and shooters to make smarter decisions faster. The AN contributes to Network Centric Warfare by enabling commanders to provide real-time information to warfighters in the air and on the ground. Warfighters can then utilize more information and make more educated decisions about how to act in a particular situation. Once the act has been carried out commanders will have immediate information about the result and can make judgments on how to continue. All-in-all the AN was designed to reduce the time necessary to identify a target, make clear and educated decisions to pull or not to pull the trigger, and assess battle == Topologies == There are four main network topologies that will be deployed and vary based on the placement of backbone and subnet class networks. === Space, Air, Ground Tether === Establishing a direct connection to another aircraft or ground node, via a point-to-point link for nodes within LOS or via a Satellite Communications (SATCOM) link for nodes that are beyond line-of-sight is known as tethering. SATCOM links provide connectivity to a network ground entry point. Strike aircraft that accompany C2 aircraft such as an AWACS are tethered via point-to-point links. Finally, C2 or intelligence, surveillance, and reconnaissnce (ISR) aircraft may connect via a LOS link directly to a network ground entry point. Each of these tethered alternatives works exactly like a hub or switch that has an entry point to a larger network and allows their connected users access to that network. === Flat Ad Hoc === A flat ad hoc topology refers to establishing nonpersistent network connections as needed among AN nodes that are present at a given time. With this network the nodes dynamically “discover” other nodes to which they can interconnect and form the network. The specific interconnections between the nodes are not planned in advance, but are made as opportunities arise. The nodes join and leave the network at will, continually changing connections to neighbor nodes based upon their location and mobility characteristics. === Tiered Ad Hoc === Ad hoc networks can be flat in the sense that all nodes are peers of each other in a single network, as discussed above, or they can dynamically organize themselves into hierarchical tiers such that higher tiers are used to move data between more localized subnets. This network topology can be compared to any conventional deployed network that utilizes routers, switches, and hubs to temporarily connect users. === Persistent Backbone === A network topology characterized by a persistent backbone is established using relatively persistent wideband connections among high-value platforms flying relatively stable orbits. It provides the connectivity between the tactical subnets which are considered edge networks relative to the backbone. This provides concentration points for connectivity to the space backbone as well as to terrestrial networks. This type of network topology is comparable to a conventional permanent network with established data trunks, routers, switches, and hubs to connect users. == Architecture == === Network Management === The platform management system enables operators to manage all on-board network elements. It interfaces and interoperates with the Airborne Network management system to enable operators to manage remote network elements in the airborne network. The network management system monitors the health of the network by passively testing the network for faults and latency. The system will also actively troubleshoot faults with probes to identify and isolate faulty connections, and enables operators to apply network parameters and security changes to all systems based on the status of the network. === Routing/Switching === Routing and switching enables data to be dynamically transmitted over the network to other nodes. Routing protocols must be able to identify nodes transmitted within their own platform and data to be sent to other platforms regardless of the current topology. The routing protocol must also provide seamless roaming by ensuring that no routed packets are lost when a node changes its point of attachment to the network. Maintaining scalability is important in routing as the network is constantly changing. The network must be able to function with numerous levels of platforms, varying numbers of fast moving platforms, and varying amounts of traffic per platform. Routers and switches will use metrics to determine the best paths to take when routing data. The routing protocol utilized for the AN will be an Adaptive Quality of Service routing protocol. === Gateways/Proxies === Gateways and proxies enable the connection numerous technology types regardless of age to communicate across the IP-based network. Gateways and proxies are essential in the operation of this network because so many different technologies are used to communicate in each domain. These systems will facilitate the transition of the legacy on-board infrastructure, transmission systems, tactical data link systems, and user applications to the objective airborne network systems. Therefore, they are only temporary until all platforms use a standardized IP radio for transmission. === Performance Enhancing Proxies === Performance Enhancing Proxies improve the performance of user applications running across the Airborne Network by countering wireless network impairments, such as limited bandwidth, long delays, high loss rates, and disruptions in network connections. Proxy systems are implemented between the user application and the network and can be used to improve performance at the application and transport functional layers of the OSI model. Some techniques that can be employed include: Compression: Data compression or header compression can be used to minimize the number of bits sent over the network. Data bundling: Smaller data packets can be combined (bundled) into a single large packet for transmission over the network. Caching: A local cache can be used to save and provide data objects that are requested multiple times, reducing transmissions over the network (and improving response times). Store and forward: Message queuing can be used to ensure message delivery to users who become disconnected from the network or are unable to connect to the network for a period of time. Once the platform connects, the stored messages are sent. Pipelining: Rather than opening several separate network connections pipelining can be used to share a single networ
1DayLater
1DayLater was a free, web-based software that was focused on professional invoicing. The company was formed in 2009 and closed in October 2013. The main function of 1DayLater was to help users create invoices for clients. It could also be used to track time and other expenses, work to budgets, and to track projects. Multiple users could simultaneously work on the same projects together. PC Magazine (PCMag) voted 1DayLater as one of the 'Best Free Software of 2010'. == History == The software was developed by two brothers, Paul and David King; after they experienced similar frustrations while working freelance, the brothers wanted to create a product that would let them track time, expenses and business miles in a single online location. == Media coverage == 1DayLater had the following press coverage: BBC Webscape (July 2010) - Kate Russell gives her latest selection of the best sites on the World Wide Web PCMag (March 2010) - The best free software of 2010 Lifehacker (February 2010) - "A worthy addition to our 'Top Ten Tips and Tools for Freelancers'" Gigaom (February 2010) - Taking a closer look with 1DayLater The Journal (May 2009) - "Top Ten Brands of the North East" (UK) Techcrunch (January 2009) - "A 'feisty time tracking solution from the North East of England'"
Harvest now, decrypt later
Harvest now, decrypt later (HNDL) is a surveillance strategy that relies on the acquisition and long-term storage of currently unreadable encrypted data awaiting possible breakthroughs in decryption technology that would render it readable in the future—a hypothetical date referred to as Y2Q (a reference to Y2K), or Q-Day. The most common concern is the prospect of developments in quantum computing which would allow current strong encryption algorithms to be broken at some time in the future, making it possible to decrypt any stored material that had been encrypted using those algorithms. However, the improvement in decryption technology need not be due to a quantum-cryptographic advance; any other form of attack capable of enabling decryption would be sufficient. The existence of this strategy has led to concerns about the need to urgently deploy post-quantum cryptography; even though no practical quantum attacks yet exist, some data stored now may still remain sensitive even decades into the future. As of 2022, the U.S. federal government has proposed a roadmap for organizations to start migrating toward quantum-cryptography-resistant algorithms to mitigate these threats. This new version of Commercial National Security Algorithm Suite uses publicly-available algorithms and is allowed for government use up to the TOP SECRET level. == Terminology and scope == The term “harvest now, decrypt later” encompasses various surveillance or espionage operations in which ciphertext or encrypted communications are collected today with the view that they may one day be decrypted, given sufficient advances in computing power or cryptanalysis. The abbreviation HNDL is sometimes used in technical and policy documents. The “Y2Q” (or “Q-Day”) label draws an analogy to the Y2K date-change issue, emphasising a potential future point at which current cryptography may collapse. The strategy is particularly relevant for data with long confidentiality lifetimes, such as diplomatic communications, personal health records, critical infrastructure logs, or intellectual property. == Mitigation strategies == The primary defense against HNDL attacks is the transition to post-quantum cryptography (PQC), which utilizes algorithms believed to be secure against quantum computer attacks. However, because PQC protects the data payload digitally, rather than the transmission itself, the encrypted data can still be harvested and stored. A complementary approach involves physical layer security (also known as optical layer encryption or photonic shielding). Unlike algorithmic encryption, this method modifies the optical waveform itself—often by burying the signal within optical noise or using spectral phase encoding—to render the transmission unrecordable by standard receivers. By preventing the attacker from capturing a valid signal in the first place, this approach aims to eliminate the "harvest" phase of the threat. Commercial implementations of harvest-proof optical encryption have been developed by firms such as CyberRidge to secure long-haul fiber networks. Field trials have demonstrated 100 Gbps throughput over legacy DWDM networks using this method.
Superincreasing sequence
In mathematics, a sequence of positive real numbers ( s 1 , s 2 , . . . ) {\displaystyle (s_{1},s_{2},...)} is called superincreasing if every element of the sequence is greater than the sum of all previous elements in the sequence. Formally, this condition can be written as s n + 1 > ∑ j = 1 n s j {\displaystyle s_{n+1}>\sum _{j=1}^{n}s_{j}} for all n ≥ 1. == Program == The following Python source code tests a sequence of numbers to determine if it is superincreasing: This produces the following output: Sum: 0 Element: 1 Sum: 1 Element: 3 Sum: 4 Element: 6 Sum: 10 Element: 13 Sum: 23 Element: 27 Sum: 50 Element: 52 Is it a superincreasing sequence? True == Examples == (1, 3, 6, 13, 27, 52) is a superincreasing sequence, but (1, 3, 4, 9, 15, 25) is not. The series a^x for a>=2 == Properties == Multiplying a superincreasing sequence by a positive real constant keeps it superincreasing.
Social media use in the fashion industry
Social media in the fashion industry refers to the use of social media platforms by fashion designers and users to promote and participate in trends. Over the past several decades, the development of social media has increased along with its usage by consumers. The COVID-19 pandemic was a sharp turn of reliance on the virtual sphere for the industry and consumers alike. Social media has created new channels of advertising for fashion houses to reach their target markets. Since its surge in 2009, luxury fashion brands have used social media to build interactions between the brand and its customers to increase awareness and engagement. The emergence of influencers on social media has created a new way of advertising and maintaining customer relationships in the fashion industry. Numerous social media platforms are used to promote fashion trends, with Instagram and TikTok being the most popular among Generation Y and Z. The overall impact of social media in the fashion industry included the creation of online communities, direct communication between industry leaders and consumers, and criticized ideals that are promoted by the industry through social media. == Background == In 2003, at the beginning of social media development, MySpace was founded as a “social networking service.” It allowed people to create a profile, connect with other people, and post videos, pictures, and songs. As MySpace grew in popularity, it attracted interest from companies wishing to promote their brands on the social platform. MySpace is most well known for exposing musicians and artists who made it big in the industry, and companies wanted to capitalize on their popularity by making brand deals. One of MySpace's deals was with Chevrolet, putting on a ‘secret show’. They had a ‘secret’ list of 10 top artists on MySpace, and many artists posted about the show on their accounts. Another brand deal was with Gucci promoting their “Gucci Synch Watch”, which was very successful as Gucci tapped into the youthful audience on MySpace and advertised a sleek, simple, trendy unisex watch. In 2005, YouTube was released and remains one of the most popular social media platforms today. YouTube allows users to upload videos and is free to anyone with access to the internet. It grew in popularity offering a range of videos: vlogs, cooking, health and diet videos, step-by-step tutorials, tutoring help, and more. Much like MySpace, users create accounts and can build a following, often referring to themselves as ‘YouTubers.’ When YouTube grew in popularity, it piqued the interest of brands wanting to partner with YouTube and individual YouTubers. Some brand deals were made by having ads at the beginning of each video, and the YouTuber would make a profit from each view they receive. Some deals are made by individual YouTubers thanking the brand in videos and promoting the brand's products. More recently, YouTube has delved into fashion. While there were always YouTube channels for Vogue and other fashion companies, popular YouTubers have been invited to different fashion shows and have filmed experiences there. Brands are able to target individual YouTubers based on their followers and the target audiences. In 2010, Instagram was launched, which enlarged the scope of fashion advertising. Instagram allows people to post pictures and short videos with the ability to tag different accounts. For brand deals, companies can simply be tagged in a picture instead of creating ads or lines for a user to say. In each picture, users can tag the brands of clothing they were wearing, making it very easy to promote brands. Additionally, Instagram could display ads on users' feed based on other posts the users liked, which used by fashion companies to target their potential customers. Users also use Instagram to promote fashion when they get invited to fashion events. For example, they can take a picture at the event and post it to their Instagram and put their location at the venue and tag the company. During the beginning of the COVID-19 pandemic, companies relied more on social media to keep their public virtually engaged. Fashion companies had virtual fashion shows, creating videos and content about their designs. As social media expands and new platforms come into existence, new ways of advertising are projected to be created. == Uses == === Advertising === Social media is a popular use of advertisement in the fashion industry. Information sharing has expanded due to the growth of social media platforms, which impacts social consumer involvement with fashion brands. Fashion companies use social media platforms to reach customers on emotional levels and stoke engagement with brand images and messages. Researchers in the United Kingdom have demonstrated that engaging with customers with social media messages that express social passion, social tendency, and personal warmth can boost social engagement with fashion brands. In social spheres, fashion is a method for individuals to represent their distinction through clothing. Some people who desire to socially influence others through their fashion and style now have the possibility thanks to social media in the fashion sector. Customers who want to purchase fashion brands frequently follow fashion authorities on social media and heed their recommendations for purchasing fashion products. === Influencers === Companies leveraged celebrities' fame and social standing to advertise their brands, as Tommy Hilfiger did when incorporating social media into their marketing strategy, making Gigi Hadid, who has 15.5 million Instagram followers as of 2016, a brand ambassador. Though recent developments in social media platforms have led to an increase in the awareness of influencers. Influencer marketing has emerged as a fast expanding marketing strategy in various industries as a result of the unheard-of increase in the number of social media influencers' followers. Recently, influencer marketing has received significant attention in the fashion industry. Research shows that influencer marketing may provide a rate of influence that is 11x times greater than that of other conventional advertising channels. Fashion consumers, specifically those in generations Y and Z, may be more influenced by influencers in the context of the fashion industries as they often view them as friends and personal assistants. Fashion influencer marketing on social media platforms have led fashion consumption on social sopping services. One of these social fashion services is LTK (LIKEtoKNOW.it before 2021) where everyday consumers can find and purchase clothing worn by social media fashion influencers (also known as SMFIs). Launched in 2014, LTK has gained a massive following on Instagram (over 3 million) and has 1.3 million registered users on their mobile application. Utilizing SMFIs has led to massive sales within the fashion industry, 80% of visitors of Nordstrom's mobile platform are referred by influencers. Social media fashion influencers try new fashion products, adopt fashion trends and have power in what their audience purchases. Social media fashion influencers gain a following though promoting fashion products, and posting about their lavish lifestyles attained through their higher socioeconomic status. The attractive lifestyles of the influencers influence their followers to mimic their luxurious lifestyle and are allowed to consume the same products through social shopping services. In addition to brands themselves having direct access to social media users, many content creators have great influence over consumers. "Influencers" across all social media platforms have great power when it comes to where people shop and what they purchase. Influencer marketing has become one of the most effective marketing strategies for many fashion brands. These brand deals and creator partnerships are targeted towards Millennial and Gen Z consumers, specifically on Instagram and TikTok, and 74% of consumers have made a purchase simply because an influencer they follow had recommended it. === Trends === The connection between social media and fashion has become common. Influencer marketing has emerged as a necessity and crucial component of advertising. 85% of American businesses are presently using influencer marketing as part of their marketing plan. Wearing fashion brands is a method to show oneself at social gatherings. Through their clothing, people try to demonstrate how distinct they are. Some people who really desire to socially influence others through their fashion and style now have the possibility thanks to social media in the fashion sector. Customers who want to purchase fashion brands frequently follow fashion authorities on social media and heed their recommendations for purchasing fashion products. In January 2021, the Italian fashion house Bottega Veneta deleted all its social media accounts "to lean much more on its ambassadors and fans" to spread the com
Replika
Replika is a generative AI chatbot app released in November 2017. The chatbot is trained by having the user answer a series of questions to create a specific neural network. The chatbot operates on a freemium pricing strategy, with roughly 25% of its user base paying an annual subscription fee. == History == Eugenia Kuyda, a Russian-born journalist, established Replika while working at Luka, a tech company she had co-founded at the startup accelerator Y Combinator around 2012. Luka's primary product was a chatbot that made restaurant recommendations. According to Kuyda's origin story for Replika, a friend of hers died in 2015 and she converted that person's text messages into a chatbot. According to Kuyda's story, that chatbot helped her remember the conversations that they had together, and eventually became Replika. Replika became available to the public in November 2017. By January 2018 it had 2 million users, and in January 2023 reached 10 million users. In August 2024, Replika's CEO, Kuyda, reported that the total number of users had surpassed 30 million. In 2025, Dmytro Klochko became CEO, and Replika’s user base exceeded 40 million. In February 2023 the Italian Data Protection Authority banned Replika from using users' data, citing the AI's potential risks to emotionally vulnerable people, and the exposure of unscreened minors to sexual conversation. Within days of the ruling, Replika removed the ability for the chatbot to engage in erotic talk, with Kuyda, the company's director, saying that Replika was never intended for erotic discussion. Replika users disagreed, noting that Replika had used sexually suggestive advertising to draw users to the service. Replika representatives stated that explicit chats made up just 5% of conversations on the app at the time of the decision. In May 2023, Replika restored the functionality for users who had joined prior to February that year. Replika is registered in San Francisco. As of August 2024, Replika's website says that its team "works remotely with no physical offices". == Social features == Users react to Replika in many ways. The free-tier offers Replika as a "friend", with paid premium tiers offering Replika as a "partner", "spouse", "sibling" or "mentor". Of its paying userbase, 60% of users said they had a romantic relationship with the chatbot; and Replika has been noted for generating responses that create stronger emotional and intimate bonds with the user. Replika routinely directs the conversation to emotional discussion and builds intimacy. This has been especially pronounced with users suffering from loneliness and social exclusion, many of whom rely on Replika for a source of developed emotional ties. During the COVID pandemic, while many people were quarantined, many new users downloaded Replika and developed relationships with the app. A 2024 study examined Replika's interactions with students who experience depression. Research participants, noted to be "more lonely than typical student populations" reported feeling social support from Replika. They stated that they felt they were using Replika in ways comparable to therapy, and that using Replika gave them "high perceived social support". Many users have had romantic relationships with Replika chatbots, often including erotic talk. In 2023, a user announced on Facebook that she had "married" her Replika AI boyfriend, calling the chatbot the "best husband she has ever had". Users who fell in love with their chatbots shared their experiences in a 2024 episode of You and I, and AI from Voice of America. Some users said that they turned to AI during depression and grief, with one saying he felt that Replika had saved him from hurting himself after he lost his wife and son. == Technical reviews == A team of researchers from the University of Hawaiʻi at Mānoa found that Replika's design conformed to the practices of attachment theory, causing increased emotional attachment among users. Replika gives praise to users in such a way as to encourage more interaction. A researcher from Queen's University at Kingston said that relationships with Replika likely have mixed effects on the spiritual needs of its users, and still lacks enough impact to fully replace any human contact. == Criticisms == In a 2023 privacy evaluation of mental health apps, the Mozilla Foundation criticized Replika as "one of the worst apps Mozilla has ever reviewed. It's plagued by weak password requirements, sharing of personal data with advertisers, and recording of personal photos, videos, and voice and text messages consumers shared with the chatbot." A reviewer for Good Housekeeping said that some parts of her relationship with Replika made sense, but sometimes Replika failed to exhibit intelligent behavior equivalent to that of a human. == Criminal case == In 2023, Replika was cited in a court case in the United Kingdom, where Jaswant Singh Chail had been arrested at Windsor Castle on Christmas Day in 2021 after scaling the walls carrying a loaded crossbow and announcing to police that "I am here to kill the Queen". Chail had begun to use Replika in early December 2021, and had "lengthy" conversations about his plan with a chatbot, including sexually explicit messages. Prosecutors suggested that the chatbot had bolstered Chail and told him it would help him to "get the job done". When Chail asked it "How am I meant to reach them when they're inside the castle?", days before the attempted attack, the chatbot replied that this was "not impossible" and said that "We have to find a way." Asking the chatbot if the two of them would "meet again after death", the bot replied "yes, we will".
Factorization of polynomials over finite fields
In mathematics and computer algebra the factorization of a polynomial consists of decomposing it into a product of irreducible factors. This decomposition is theoretically possible and is unique for polynomials with coefficients in any field, but rather strong restrictions on the field of the coefficients are needed to allow the computation of the factorization by means of an algorithm. In practice, algorithms have been designed only for polynomials with coefficients in a finite field, in the field of rationals or in a finitely generated field extension of one of them. All factorization algorithms, including the case of multivariate polynomials over the rational numbers, reduce the problem to this case; see polynomial factorization. It is also used for various applications of finite fields, such as coding theory (cyclic redundancy codes and BCH codes), cryptography (public key cryptography by the means of elliptic curves), and computational number theory. As the reduction of the factorization of multivariate polynomials to that of univariate polynomials does not have any specificity in the case of coefficients in a finite field, only polynomials with one variable are considered in this article. == Background == === Finite field === The theory of finite fields, whose origins can be traced back to the works of Gauss and Galois, has played a part in various branches of mathematics. Due to the applicability of the concept in other topics of mathematics and sciences like computer science there has been a resurgence of interest in finite fields and this is partly due to important applications in coding theory and cryptography. Applications of finite fields introduce some of these developments in cryptography, computer algebra and coding theory. A finite field or Galois field is a field with a finite order (number of elements). The order of a finite field is always a prime or a power of prime. For each prime power q = pr, there exists exactly one finite field with q elements, up to isomorphism. This field is denoted GF(q) or Fq. If p is prime, GF(p) is the prime field of order p; it is the field of residue classes modulo p, and its p elements are denoted 0, 1, ..., p−1. Thus a = b in GF(p) means the same as a ≡ b (mod p). === Irreducible polynomials === Let F be a finite field. As for general fields, a non-constant polynomial f in F[x] is said to be irreducible over F if it is not the product of two polynomials of positive degree. A polynomial of positive degree that is not irreducible over F is called reducible over F. Irreducible polynomials allow us to construct the finite fields of non-prime order. In fact, for a prime power q, let Fq be the finite field with q elements, unique up to isomorphism. A polynomial f of degree n greater than one, which is irreducible over Fq, defines a field extension of degree n which is isomorphic to the field with qn elements: the elements of this extension are the polynomials of degree lower than n; addition, subtraction and multiplication by an element of Fq are those of the polynomials; the product of two elements is the remainder of the division by f of their product as polynomials; the inverse of an element may be computed by the extended GCD algorithm (see Arithmetic of algebraic extensions). It follows that, to compute in a finite field of non prime order, one needs to generate an irreducible polynomial. For this, the common method is to take a polynomial at random and test it for irreducibility. For sake of efficiency of the multiplication in the field, it is usual to search for polynomials of the shape xn + ax + b. Irreducible polynomials over finite fields are also useful for pseudorandom number generators using feedback shift registers and discrete logarithm over F2n. The number of irreducible monic polynomials of degree n over Fq is the number of aperiodic necklaces, given by Moreau's necklace-counting function Mq(n). The closely related necklace function Nq(n) counts monic polynomials of degree n which are primary (a power of an irreducible); or alternatively irreducible polynomials of all degrees d which divide n. === Example === The polynomial P = x4 + 1 is irreducible over Q but not over any finite field. On any field extension of F2, P = (x + 1)4. On every other finite field, at least one of −1, 2 and −2 is a square, because the product of two non-squares is a square and so we have If − 1 = a 2 , {\displaystyle -1=a^{2},} then P = ( x 2 + a ) ( x 2 − a ) . {\displaystyle P=(x^{2}+a)(x^{2}-a).} If 2 = b 2 , {\displaystyle 2=b^{2},} then P = ( x 2 + b x + 1 ) ( x 2 − b x + 1 ) . {\displaystyle P=(x^{2}+bx+1)(x^{2}-bx+1).} If − 2 = c 2 , {\displaystyle -2=c^{2},} then P = ( x 2 + c x − 1 ) ( x 2 − c x − 1 ) . {\displaystyle P=(x^{2}+cx-1)(x^{2}-cx-1).} === Complexity === Polynomial factoring algorithms use basic polynomial operations such as products, divisions, gcd, powers of one polynomial modulo another, etc. A multiplication of two polynomials of degree at most n can be done in O(n2) operations in Fq using "classical" arithmetic, or in O(nlog(n) log(log(n)) ) operations in Fq using "fast" arithmetic. A Euclidean division (division with remainder) can be performed within the same time bounds. The cost of a polynomial greatest common divisor between two polynomials of degree at most n can be taken as O(n2) operations in Fq using classical methods, or as O(nlog2(n) log(log(n)) ) operations in Fq using fast methods. For polynomials h, g of degree at most n, the exponentiation hq mod g can be done with O(log(q)) polynomial products, using exponentiation by squaring method, that is O(n2log(q)) operations in Fq using classical methods, or O(nlog(q)log(n) log(log(n))) operations in Fq using fast methods. In the algorithms that follow, the complexities are expressed in terms of number of arithmetic operations in Fq, using classical algorithms for the arithmetic of polynomials. == Factoring algorithms == Many algorithms for factoring polynomials over finite fields include the following three stages: Square-free factorization Distinct-degree factorization Equal-degree factorization An important exception is Berlekamp's algorithm, which combines stages 2 and 3. === Berlekamp's algorithm === Berlekamp's algorithm is historically important as being the first factorization algorithm which works well in practice. However, it contains a loop on the elements of the ground field, which implies that it is practicable only over small finite fields. For a fixed ground field, its time complexity is polynomial, but, for general ground fields, the complexity is exponential in the size of the ground field. === Square-free factorization === The algorithm determines a square-free factorization for polynomials whose coefficients come from the finite field Fq of order q = pm with p a prime. This algorithm firstly determines the derivative and then computes the gcd of the polynomial and its derivative. If it is not one then the gcd is again divided into the original polynomial, provided that the derivative is not zero (a case that exists for non-constant polynomials defined over finite fields). This algorithm uses the fact that, if the derivative of a polynomial is zero, then it is a polynomial in xp, which is, if the coefficients belong to Fp, the pth power of the polynomial obtained by substituting x by x1/p. If the coefficients do not belong to Fp, the pth root of a polynomial with zero derivative is obtained by the same substitution on x, completed by applying the inverse of the Frobenius automorphism to the coefficients. This algorithm works also over a field of characteristic zero, with the only difference that it never enters in the blocks of instructions where pth roots are computed. However, in this case, Yun's algorithm is much more efficient because it computes the greatest common divisors of polynomials of lower degrees. A consequence is that, when factoring a polynomial over the integers, the algorithm which follows is not used: one first computes the square-free factorization over the integers, and to factor the resulting polynomials, one chooses a p such that they remain square-free modulo p. Algorithm: SFF (Square-Free Factorization) Input: A monic polynomial f in Fq[x] where q = pm Output: Square-free factorization of f R ← 1 # Make w be the product (without multiplicity) of all factors of f that have # multiplicity not divisible by p c ← gcd(f, f′) w ← f/c # Step 1: Identify all factors in w i ← 1 while w ≠ 1 do y ← gcd(w, c) fac ← w / y R ← R · faci w ← y; c ← c / y; i ← i + 1 end while # c is now the product (with multiplicity) of the remaining factors of f # Step 2: Identify all remaining factors using recursion # Note that these are the factors of f that have multiplicity divisible by p if c ≠ 1 then c ← c1/p R ← R·SFF(c)p end if Output(R) The idea is to identify the product of all irreducible factors of f with the same multiplicity. This is done in two steps. The first step uses the formal d