Friending and following

Friending is the act of adding someone to a list of "friends" on a social networking service. The notion does not necessarily involve the concept of friendship. It is also distinct from the idea of a "fan"—as employed on the WWW sites of businesses, bands, artists, and others—since it is more than a one-way relationship. A "fan" only receives things. A "friend" can communicate back to the person friending. The act of "friending" someone usually grants that person special privileges (on the service) with respect to oneself. On Facebook, for example, one's "friends" have the privilege of viewing and posting to one's "timeline". Following is a similar concept on other social network services, such as Twitter and Instagram, where a person (follower) chooses to add content from a person or page to their newsfeed. Unlike friending, following is not necessarily mutual, and a person can unfollow (stop following) or block another user at any time without affecting that user's following status. The first scholarly definition and examination of friending and defriending (the act of removing someone from one's friend list, also called unfriending) was David Fono and Kate Raynes-Goldie's "Hyperfriendship and beyond: Friends and Social Norms on LiveJournal" from 2005, which identified the use of the term as both a noun and a verb by users of early social network site and blogging platform LiveJournal, which was originally launched in 1999. == Friend/follower count, friend collecting, and multiple accounts == The addition of people to a friend list without regard to whether one actually is their friend is sometimes known as friend whoring. Matt Jones of Dopplr went so far as to coin the expression "friending considered harmful" to describe the problem of focusing upon the friending of more and more people at the expense of actually making any use of a social network. Friend collecting is the adding of hundreds or thousands of friends/followers, a not uncommon order of magnitude on some social sites. As a result, many teen users feel pressured to heavily curate their posts, posting only carefully posed and edited photographs with well-thought-out captions. Some Instagram users will create a second account, known as a Finsta (short for "Fake Instagram"). A Finsta is typically private, and the owner only allows close friends to follow it. Since the follower count is kept down, the posts can be more candid and silly in nature. Users may also create multiple accounts based on their interests. Someone with a personal social media account might be a photographer and maintain a separate account for that. There is risk associated with following large numbers of people: scholars say that social anxiety could be an effect of managing a large social media network, as users can feel jealous and have a "fear of missing out". == Unfriending and unfollowing == Unfriending is the act of removing someone from a friends list. On Facebook, this means the action is unilateral, meaning, the friendship is terminated on both sides. The act of unfriending is often used when one user was flirting and made the other uncomfortable. Unfollowing is a little different. When a user unfollows someone on Instagram or Twitter, it continues a one-sided relationship. Often, the unfollowed user doesn't realize they were unfollowed, so they continue the following. == Social network friending and friendship == There are distinct groups of "friends" that one can friend on a social networking service. The notion of a social network friend does not necessarily embody the concept of friendship. Although terminology has not yet evolved to distinguish the different types of social networking friends, they can be broken into the following three categories. friends who are actually known These are people that may be one's friends or family in real life, with whom one has regular interaction either on-line or off-line. organizational friends These are companies and other organizations who maintain a "friending" relationship as a contacts list. complete strangers These are social networking "friends" with whom one has no relationship at all. Within these categories "friends" can be made up of strong ties, weak existing ties, weak latent ties, and parasocial ties. Strong ties can be made up of close family members and friends where self-disclosure, intimacy and frequent content occur. Weak existing ties can be made up of acquaintances, co-workers and distance relatives with whom the user has inconsistent contact. Weak latent ties can be made up of people within a similar geographical location or profession that can be used as a potential future bridge to other connections. Parasocial ties can be made up of celebrities, public figures and media personas. Human nature is to reciprocate a friending, marking someone as a friend who has marked oneself as a friend. This is a social norm for social networking services. However, this leads to mixing up who is an actual friend, and who is a contact. Tagging someone as a "contact" who has marked one as a "friend" can be perceived as impolite. Other concerns about this issue are treated in Sherry Turkle's Alone Together which analyses many behavioral dynamics in social media friendships. Turkle defines herself as "cautiously optimistic", but expresses concern that distance communications may undermine genuine face-to-face spoken discourses, lessening people's expectations of one another. One social networking service, FriendFeed, allows one to friend someone as a "fake" friend. The person "fake" friended receives the usual notifications for friending, but that person's updates are not received. Gavin Bell, author of Building Social Web Applications, describes this mechanism as "ludicrous". Results from a 2007 survey the Center for the Digital Future stated that only 23% of internet users have at least one virtual friend whom they have only met online. Ideally the number of virtual friends is directly proportional to the use of the Internet, but the same survey showed 20% of heavy-users (more than 3 hours/day) who claimed an average of 8.7% online friends, reported at least one relationship that started virtually and migrated to in-person contact. This results and other concerning issues are included in the book Networked: The New Social Operating System co-written by Lee Rainie and Barry Wellman in 2012. == Ethical considerations == The act of "friending" someone on a social networking service has particular ethical implications for judges in the United States. Judicial codes of conducts in the various states generally incorporate some form of provision that judges should avoid even the appearance of impropriety. Whether this regulates and even prohibits judges "friending" attorneys that appear before them, and law enforcement personnel, has been the subject of some analysis by the judicial ethics panels of the various states. They haven't all agreed on the guidance that they have given to judges: The New York state Judicial Ethics committee in 2009 simply advised judges to employ caution, noting that the issue of "friending" someone on a social networking service is a publicly observable act that has little difference from other public behavior concerns judges already face. The Florida Judicial Ethics Advisory committee in 2009 noted that, judges being normal human beings, it was unavoidable for judges to form friendships without the responsibilities of their job. It prohibited judges from friending any attorneys that appeared before them, whilst allowing friending of those who do not, on the grounds that it may give the appearance to the general public (even if the substance is otherwise) that those attorneys who are friended hold special sway with the judge. A minority opinion of the committee asserted that there is a substantive difference between "friending" on a social networking service and actual friendship, and that the general public, being aware of the norms of social networking services, was capable of drawing this distinction and would not reasonably conclude either a special degree of influence or a violation of the code of judicial conduct. This minority opinion was outnumbered twice in 2009, both in the Judicial Ethics Advisory and in the Florida Supreme Court Judicial Ethics Advisory committee. The South Carolina judicial conduct committee in 2009 permitted judges to friend attorneys and law enforcement personnel, with the proviso that no judicial business should be conducted upon nor discussed via the social networking service. "... a judge should not become isolated from the community in which the judge lives.", the committee stated. The Kentucky Judicial Ethics committee in 2010 took the same position as the minority opinion in Florida. It urged judges to exercise caution, but recognized that the act of friending "does not, in and of itself, indicate the degree or intensity of a judge's relationship with the person who is the 'friend'

PatchMatch

PatchMatch is an algorithm used to quickly find correspondences (or matches) between small square regions (or patches) of an image. It has various applications in image editing, such as reshuffling or removing objects from images or altering their aspect ratios without cropping or noticeably stretching them. PatchMatch was first presented in a 2011 paper by researchers at Princeton University. == Algorithm == The goal of the algorithm is to find the patch correspondence by defining a nearest-neighbor field (NNF) as a function f : R 2 → R 2 {\displaystyle f:\mathbb {R} ^{2}\to \mathbb {R} ^{2}} of offsets, which is over all possible matches of patch (location of patch centers) in image A, for some distance function of two patches D {\displaystyle D} . So, for a given patch coordinate a {\displaystyle a} in image A {\displaystyle A} and its corresponding nearest neighbor b {\displaystyle b} in image B {\displaystyle B} , f ( a ) {\displaystyle f(a)} is simply b − a {\displaystyle b-a} . However, if we search for every point in image B {\displaystyle B} , the work will be too hard to complete. So the following algorithm is done in a randomized approach in order to accelerate the calculation speed. The algorithm has three main components. Initially, the nearest-neighbor field is filled with either random offsets or some prior information. Next, an iterative update process is applied to the NNF, in which good patch offsets are propagated to adjacent pixels, followed by random search in the neighborhood of the best offset found so far. Independent of these three components, the algorithm also uses a coarse-to-fine approach by building an image pyramid to obtain the better result. === Initialization === When initializing with random offsets, we use independent uniform samples across the full range of image B {\displaystyle B} . This algorithm avoids using an initial guess from the previous level of the pyramid because in this way the algorithm can avoid being trapped in local minima. === Iteration === After initialization, the algorithm attempted to perform iterative process of improving the N N F {\displaystyle NNF} . The iterations examine the offsets in scan order (from left to right, top to bottom), and each undergoes propagation followed by random search. === Propagation === We attempt to improve f ( x , y ) {\displaystyle f(x,y)} using the known offsets of f ( x − 1 , y ) {\displaystyle f(x-1,y)} and f ( x , y − 1 ) {\displaystyle f(x,y-1)} , assuming that the patch offsets are likely to be the same. That is, the algorithm will take new value for f ( x , y ) {\displaystyle f(x,y)} to be arg ⁡ min ( x , y ) D ( f ( x , y ) ) , D ( f ( x − 1 , y ) ) , D ( f ( x , y − 1 ) ) {\displaystyle \arg \min \limits _{(x,y)}{D(f(x,y)),D(f(x-1,y)),D(f(x,y-1))}} . So if f ( x , y ) {\displaystyle f(x,y)} has a correct mapping and is in a coherent region R {\displaystyle R} , then all of R {\displaystyle R} below and to the right of f ( x , y ) {\displaystyle f(x,y)} will be filled with the correct mapping. Alternatively, on even iterations, the algorithm search for different direction, fill the new value to be arg ⁡ min ( x , y ) { D ( f ( x , y ) ) , D ( f ( x + 1 , y ) ) , D ( f ( x , y + 1 ) ) } {\displaystyle \arg \min \limits _{(x,y)}\{D(f(x,y)),D(f(x+1,y)),D(f(x,y+1))\}} . === Random search === Let v 0 = f ( x , y ) {\displaystyle v_{0}=f(x,y)} , we attempt to improve f ( x , y ) {\displaystyle f(x,y)} by testing a sequence of candidate offsets at an exponentially decreasing distance from v 0 {\displaystyle v_{0}} u i = v 0 + w α i R i {\displaystyle u_{i}=v_{0}+w\alpha ^{i}R_{i}} where R i {\displaystyle R_{i}} is a uniform random in [ − 1 , 1 ] × [ − 1 , 1 ] {\displaystyle [-1,1]\times [-1,1]} , w {\displaystyle w} is a large window search radius which will be set to maximum picture size, and α {\displaystyle \alpha } is a fixed ratio often assigned as 1/2. This part of the algorithm allows the f ( x , y ) {\displaystyle f(x,y)} to jump out of local minimum through random process. === Halting criterion === The often used halting criterion is set the iteration times to be about 4~5. Even with low iteration, the algorithm works well.

Data stream management system

A data stream management system (DSMS) is a computer software system to manage continuous data streams. It is similar to a database management system (DBMS), which is, however, designed for static data in conventional databases. A DBMS also offers a flexible query processing so that the information needed can be expressed using queries. However, in contrast to a DBMS, a DSMS executes a continuous query that is not only performed once, but is permanently installed. Therefore, the query is continuously executed until it is explicitly uninstalled. Since most DSMS are data-driven, a continuous query produces new results as long as new data arrive at the system. This basic concept is similar to complex event processing so that both technologies are partially coalescing. == Functional principle == One important feature of a DSMS is the possibility to handle potentially infinite and rapidly changing data streams by offering flexible processing at the same time, although there are only limited resources such as main memory. The following table provides various principles of DSMS and compares them to traditional DBMS. == Processing and streaming models == One of the biggest challenges for a DSMS is to handle potentially infinite data streams using a fixed amount of memory and no random access to the data. There are different approaches to limit the amount of data in one pass, which can be divided into two classes. For the one hand, there are compression techniques that try to summarize the data and for the other hand there are window techniques that try to portion the data into (finite) parts. === Synopses === The idea behind compression techniques is to maintain only a synopsis of the data, but not all (raw) data points of the data stream. The algorithms range from selecting random data points called sampling to summarization using histograms, wavelets or sketching. One simple example of a compression is the continuous calculation of an average. Instead of memorizing each data point, the synopsis only holds the sum and the number of items. The average can be calculated by dividing the sum by the number. However, it should be mentioned that synopses cannot reflect the data accurately. Thus, a processing that is based on synopses may produce inaccurate results. === Windows === Instead of using synopses to compress the characteristics of the whole data streams, window techniques only look on a portion of the data. This approach is motivated by the idea that only the most recent data are relevant. Therefore, a window continuously cuts out a part of the data stream, e.g. the last ten data stream elements, and only considers these elements during the processing. There are different kinds of such windows like sliding windows that are similar to FIFO lists or tumbling windows that cut out disjoint parts. Furthermore, the windows can also be differentiated into element-based windows, e.g., to consider the last ten elements, or time-based windows, e.g., to consider the last ten seconds of data. There are also different approaches to implementing windows. There are, for example, approaches that use timestamps or time intervals for system-wide windows or buffer-based windows for each single processing step. Sliding-window query processing is also suitable to being implemented in parallel processors by exploiting parallelism between different windows and/or within each window extent. == Query processing == Since there are a lot of prototypes, there is no standardized architecture. However, most DSMS are based on the query processing in DBMS by using declarative languages to express queries, which are translated into a plan of operators. These plans can be optimized and executed. A query processing often consists of the following steps. === Formulation of continuous queries === The formulation of queries is mostly done using declarative languages like SQL in DBMS. Since there are no standardized query languages to express continuous queries, there are a lot of languages and variations. However, most of them are based on SQL, such as the Continuous Query Language (CQL), StreamSQL and ESP. There are also graphical approaches where each processing step is a box and the processing flow is expressed by arrows between the boxes. The language strongly depends on the processing model. For example, if windows are used for the processing, the definition of a window has to be expressed. In StreamSQL, a query with a sliding window for the last 10 elements looks like follows: This stream continuously calculates the average value of "price" of the last 10 tuples, but only considers those tuples whose prices are greater than 100.0. In the next step, the declarative query is translated into a logical query plan. A query plan is a directed graph where the nodes are operators and the edges describe the processing flow. Each operator in the query plan encapsulates the semantic of a specific operation, such as filtering or aggregation. In DSMSs that process relational data streams, the operators are equal or similar to the operators of the Relational algebra, so that there are operators for selection, projection, join, and set operations. This operator concept allows the very flexible and versatile processing of a DSMS. === Optimization of queries === The logical query plan can be optimized, which strongly depends on the streaming model. The basic concepts for optimizing continuous queries are equal to those from database systems. If there are relational data streams and the logical query plan is based on relational operators from the Relational algebra, a query optimizer can use the algebraic equivalences to optimize the plan. These may be, for example, to push selection operators down to the sources, because they are not so computationally intensive like join operators. Furthermore, there are also cost-based optimization techniques like in DBMS, where a query plan with the lowest costs is chosen from different equivalent query plans. One example is to choose the order of two successive join operators. In DBMS this decision is mostly done by certain statistics of the involved databases. But, since the data of a data streams is unknown in advance, there are no such statistics in a DSMS. However, it is possible to observe a data stream for a certain time to obtain some statistics. Using these statistics, the query can also be optimized later. So, in contrast to a DBMS, some DSMS allows to optimize the query even during runtime. Therefore, a DSMS needs some plan migration strategies to replace a running query plan with a new one. === Transformation of queries === Since a logical operator is only responsible for the semantics of an operation but does not consist of any algorithms, the logical query plan must be transformed into an executable counterpart. This is called a physical query plan. The distinction between a logical and a physical operator plan allows more than one implementation for the same logical operator. The join, for example, is logically the same, although it can be implemented by different algorithms like a Nested loop join or a Sort-merge join. Notice, these algorithms also strongly depend on the used stream and processing model. Finally, the query is available as a physical query plan. === Execution of queries === Since the physical query plan consists of executable algorithms, it can be directly executed. For this, the physical query plan is installed into the system. The bottom of the graph (of the query plan) is connected to the incoming sources, which can be everything like connectors to sensors. The top of the graph is connected to the outgoing sinks, which may be for example a visualization. Since most DSMSs are data-driven, a query is executed by pushing the incoming data elements from the source through the query plan to the sink. Each time when a data element passes an operator, the operator performs its specific operation on the data element and forwards the result to all successive operators. == Examples == AURORA, StreamBase Systems, Inc. Archived 23 March 2009 at the Wayback Machine Hortonworks DataFlow IBM Streams NIAGARA Query Engine NiagaraST: A Research Data Stream Management System at Portland State University Odysseus, an open source Java-based framework for Data Stream Management Systems Pipeline DB PIPES Archived 24 December 2016 at the Wayback Machine, webMethods Business Events QStream SAS Event Stream Processing SQLstream STREAM StreamGlobe StreamInsight TelegraphCQ WSO2 Stream Processor

Software token

A software token (a.k.a. soft token) is a piece of a two-factor authentication security device that may be used to authorize the use of computer services. Software tokens are stored on a general-purpose electronic device such as a desktop computer, laptop, PDA, or mobile phone and can be duplicated. (Contrast hardware tokens, where the credentials are stored on a dedicated hardware device and therefore cannot be duplicated — absent physical invasion of the device) Because software tokens are something one does not physically possess, they are exposed to unique threats based on duplication of the underlying cryptographic material - for example, computer viruses and software attacks. Both hardware and software tokens are vulnerable to bot-based man-in-the-middle attacks, or to simple phishing attacks in which the one-time password provided by the token is solicited, and then supplied to the genuine website in a timely manner. Software tokens do have benefits: there is no physical token to carry, they do not contain batteries that will run out, and they are cheaper than hardware tokens. == Security architecture == There are two primary architectures for software tokens: shared secret and public-key cryptography. For a shared secret, an administrator will typically generate a configuration file for each end-user. The file will contain a username, a personal identification number, and the secret. This configuration file is given to the user. The shared secret architecture is potentially vulnerable in a number of areas. The configuration file can be compromised if it is stolen and the token is copied. With time-based software tokens, it is possible to borrow an individual's PDA or laptop, set the clock forward, and generate codes that will be valid in the future. Any software token that uses shared secrets and stores the PIN alongside the shared secret in a software client can be stolen and subjected to offline attacks. Shared secret tokens can be difficult to distribute, since each token is essentially a different piece of software. Each user must receive a copy of the secret, which can create time constraints. Some newer software tokens rely on public-key cryptography, or asymmetric cryptography. This architecture eliminates some of the traditional weaknesses of software tokens, but does not affect their primary weakness (ability to duplicate). A PIN can be stored on a remote authentication server instead of with the token client, making a stolen software token no good unless the PIN is known as well. However, in the case of a virus infection, the cryptographic material can be duplicated and then the PIN can be captured (via keylogging or similar) the next time the user authenticates. If there are attempts made to guess the PIN, it can be detected and logged on the authentication server, which can disable the token. Using asymmetric cryptography also simplifies implementation, since the token client can generate its own key pair and exchange public keys with the server.

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

Toolchain

A toolchain is a set of software development tools used to build and otherwise develop software. Often, the tools are executed sequentially and form a pipeline such that the output of one tool is the input for the next. Sometimes the term is used for a set of related tools that are not necessarily executed sequentially. A relatively common and simple toolchain consists of the tools to build for a particular operating system (OS) and CPU architecture: a compiler, a linker, and a debugger. With a cross-compiler, a toolchain can support cross-platform development. For building more complex software systems, many other tools may be in the toolchain. For example, for a video game, the toolchain may include tools for preparing sound effects, music, textures, 3-dimensional models and animations, and for combining these resources into the finished product.

PatchMatch

Data stream management system

Software token

Factorization of polynomials over finite fields

Toolchain

Factorization of polynomials over finite fields

Related Articles